Project Euler

Problem #43

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d_(1) be the 1^(st) digit, d_(2) be the 2^(nd) digit, and so on. In this way, we note the following:

  • d_(2)d_(3)d_(4)=406 is divisible by 2
  • d_(3)d_(4)d_(5)=063 is divisible by 3
  • d_(4)d_(5)d_(6)=635 is divisible by 5
  • d_(5)d_(6)d_(7)=357 is divisible by 7
  • d_(6)d_(7)d_(8)=572 is divisible by 11
  • d_(7)d_(8)d_(9)=728 is divisible by 13
  • d_(8)d_(9)d_(10)=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

Erlang: Running time = 0.1s
+%run_procs

+%digit_split

p43()->
	put(digs,lists:seq(0,9)),
	Ans=run_procs(1000 div 17,fun(I)->[euler,p43,[gocalc,I*17,get(digs),self()]] end,
				  fun(A,{done,B})->A+B end,0),
	io:format("~w~n",[Ans]).
p43(calc,Digs,[])->[Digs];
p43(calc,Digs,Rem)->
	Prime=element(length(Rem),{1,2,3,5,7,11,13}),
	[Ten,One|_]=Digs,
	Possible=lists:filter(fun(N)->
					(100*N+10*Ten+One) rem Prime == 0 end,
				Rem),
	lists:append(lists:map(fun(D)->p43(calc,[D|Digs],lists:delete(D,Rem)) end, Possible)).
p43(gocalc,N,DigsAll,Parent)->
	Digs1=digit_split(N),
	Digs=case length(Digs1) of
		2->["0"|Digs1];
		3->Digs1
	end,
	Rem=lists:subtract(DigsAll,Digs),
	case length(Rem)==7 of
		true->
			DigsRes=p43(calc,Digs,Rem),
			Res=lists:map(fun(D)->
						list_to_integer(lists:append(
							lists:map(fun integer_to_list/1,D))) end,DigsRes),
			Parent ! {done, lists:sum(Res)};
		false-> Parent ! {done, 0}
	end.

Ruby: Running time = 0.02s
+#Enumerable

def pad(n,d)
  s=n.to_s
  return s if s.length>=d
  ("0"*(d-s.length))+s
end

def p43
  digs=(0..9).map{|i|i.to_s}
  results=(1..(1000/17)).map{|i|pad(17*i,3)}.reject{|s|s.length>s.split("").uniq.length}
  [13,11,7,5,3,2,1].each do |p|
    results.map!{|s|digs.reject{|d|s.index(d)}.select{|d|(d+s[0..1]).to_i%p==0}.map{|d|d+s}}.flatten!
  end
  puts results.map{|s|s.to_i}.sum
end