       Re: challenge problem

• To: mathgroup at smc.vnet.net
• Subject: [mg61286] Re: challenge problem
• Date: Fri, 14 Oct 2005 05:55:34 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

```On 10/13/05 at 1:39 AM, murray at math.umass.edu (Murray Eisenberg)
wrote:

>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.

Hmm... On my 32-bit MaxOS X machine Mathematica 5.2 doesn't complain about generating large integers. For example,

In:=
Range[10^19, 5 + 10^19]
Out=
{10000000000000000000,
10000000000000000001,
10000000000000000002,
10000000000000000003,
10000000000000000004,
10000000000000000005}

But be this as it may, I don't think you want to solve this problem by mapping a function to Range[10^11] even if you had a 64-bit machine.

Consider

In:=
Table[Timing[Total[
Select[Select[Range[10^(n - 1), 10^n - 1],
Mod[#1, 7] == 0 & ], Mod[FromDigits[Reverse[
IntegerDigits[ #1]]], 7] == 0 & ]]], {n, 6}]
Out=
{{0.0010 Second, 7},
{0.0014 Second, 147},
{0.0115 Second, 10633},
{0.1241 Second, 1018780},
{1.2649 Second, 104684559},
{12.447 Second, 10258275510}}

Clearly, the execution time is increasing exponentially. So, while there is probably a faster method for selecting numbers meeting the specified criteria and faster machines than the one I am using, I doubt using this approach will have an acceptable execution time.

Also note the number of integers between 10^(n-1) and 10^n -1 meeting the criteria increases exponentially, i.e.

n   number of values meeting criteria

1   1
2   2
3   18
4   184
5   1907
6   18615

So, the execution time for any algorithm selecting values between 1 and 10^n meeting the criteria must increase exponentially.
--
To reply via email subtract one hundred and four

```

• Prev by Date: Re: No visualisation of unmatched brackets anymore
• Next by Date: Re: Shadowing of symbols in a package
• Previous by thread: Re: challenge problem
• Next by thread: Re: challenge problem