[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
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**
| |