[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