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