       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:=
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:=
(* 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=
{190.234 Second,Null}
In:=
(* 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=
{12.094 Second,Null}
In:=
(* 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[]]]],
IntegerDigits[list1[[n[]]]] } ]]]

Map[h,randlist]
Out=
{2112,20727}
Out=
{{2024,17511},{869,20621},{916,10566},{171,17546},{841,15711},{1479,412},{27
1,
13463},{1434,14217},{1720,16296},{570,16054}}
Out=
{{True,True},{True,True},{True,True},{True,True},{True,True},{True,
True},{True,True},{True,True},{True,True},{True,True}}
In:=
\!\(\(\( (*\
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=
{105714126,10363989636}
Out=
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