[Date Index]
[Thread Index]
[Author Index]
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
Prev by Date:
**Re: DSolve and matrix form of system of equations**
Next by Date:
**Re: Solving Diophantine Equations**
Previous by thread:
**Re: challenge problem**
Next by thread:
**Re: challenge problem**
| |