[Date Index] [Thread Index] [Author Index]

Re: challenge problem

• To: mathgroup at smc.vnet.net
• Subject: [mg61286] Re: challenge problem
• From: Bill Rowe <readnewsciv at earthlink.net>
• 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[94]:=
Range[10^19, 5 + 10^19]
Out[94]=
{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[89]:=
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[89]=
{{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