Re: challenge problem
- To: mathgroup at smc.vnet.net
- Subject: [mg61309] Re: challenge problem
- From: Fred Bartoli <fred._canxxxel_this_bartoli at RemoveThatAlso_free.fr_AndThisToo>
- Date: Fri, 14 Oct 2005 22:22:43 -0400 (EDT)
- References: <diksl6$4n8$1@smc.vnet.net>
- Reply-to: Fred Bartoli <fred._canxxxel_this_bartoli at RemoveThatAlso_free.fr_AndThisToo>
- Sender: owner-wri-mathgroup at wolfram.com
"Murray Eisenberg" <murray at math.umass.edu> a écrit dans le message de news:diksl6$4n8$1 at smc.vnet.net... > At http://www.itasoftware.com/careers/eng/job1.php, there are a number > of interestng programming problems posed. One, the "Lucky Sevens", is > to write a program that will find the sum of all those integers between > 1 and 10^11 that are divisible by 7 AND whose reversed-digit forms are > also divisible by 7. > > I should think that an elegant and possibly efficient solution in > Mathematica would be to use the form func /@ Range[10^11]. But since > Mathematica 5.2 on my my 32-bit Windows machine won't let me form > Range[10^11], a 64-bit architecture would seem to be required. > > Hello, I'm a long time lurker here and found this little pb funny, so here's how I'd do it. The answer is 2191158578348111232 and took only 3 min on my P2/400 using semi brut force. I'll use Pascal's test (see http://mathworld.wolfram.com/DivisibilityTests.html ) A number bellow 10^6 and divisible by 7 must have its 6 digits satisfying the following: Mod[ a0 + 3 a1 + 2 a2 - a3 - 3 a4 - 2 a5, 7] == 0 A number bellow 10^6 whose reversed digits sequence is divisible by 7 must have its 6 digits satisfying the following: Mod[ a5 + 3 a4 + 2 a3 - a2 - 3 a1 - 2 a0, 7] == 0 For numbers above 10^6, the sequence repeats for the next six digits packet and so on... Code follows. -- Thanks, Fred. In[273]:= DivisibleBy[7,n_]:=Module[{d}, Mod[NestWhile[FromDigits[Most[d=IntegerDigits[#]]]-2Last[d]&,n,Positive], 7]\[Equal]0 ] reverseTest=DivisibleBy[7,FromDigits[Reverse[IntegerDigits[#]]]]&; In[275]:= (* use brut force to compute all the numbers bellow 10^6 satisfying the \ criteria *) list1={}; For[i=7,i<1000000,i=i+7,If[reverseTest[i],AppendTo[list1,i]] ]//Timing Out[276]= {190.234 Second,Null} In[277]:= (* use brut force to compute all the numbers bellow 10^5 satisfying the \ criteria *) list2={}; For[i=7,i<100000,i=i+7,If[reverseTest[i],AppendTo[list2,i]] ]//Timing Out[278]= {12.094 Second,Null} In[352]:= (* Any number satisfying the divisibility and reverse divisibility criterias \ can be made by randomly choosing its first 5 digits sequence in the first \ list and its last 6 digits sequence in second list *) (* test some *) testNumber={reverseTest[#],DivisibleBy[7,#]}&; {len2,len1}=Map[Length,{list2,list1}] randlist=Table[Map[Random[Integer,{1,#}]&,{len2,len1}],{i,10}] h[n_]:=testNumber[ FromDigits[ Flatten[{IntegerDigits[list2[[n[[1]]]]], IntegerDigits[list1[[n[[2]]]]] } ]]] Map[h,randlist] Out[353]= {2112,20727} Out[354]= {{2024,17511},{869,20621},{916,10566},{171,17546},{841,15711},{1479,412},{27 1, 13463},{1434,14217},{1720,16296},{570,16054}} Out[356]= {{True,True},{True,True},{True,True},{True,True},{True,True},{True, True},{True,True},{True,True},{True,True},{True,True}} In[357]:= \!\(\(\( (*\ We\ now\ just\ have\ to\ do\ the\ sums\ \ *) \)\(\[IndentingNewLine]\)\({sum2, sum1} = Map[Apply[Plus, #] &, {list2, list1}]\[IndentingNewLine]\[IndentingNewLine] problemsum = sum1\ len2\ + \ 10\^6\ len1\ \ sum2\)\)\) Out[357]= {105714126,10363989636} Out[358]= 2191158578348111232