MathGroup Archive 2007

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

Search the Archive

Re: Re: request for a few minutes CPU-time

  • To: mathgroup at smc.vnet.net
  • Subject: [mg79814] Re: [mg79521] Re: [mg79477] request for a few minutes CPU-time
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Sun, 5 Aug 2007 04:55:21 -0400 (EDT)
  • References: <200707271001.GAA03340@smc.vnet.net> <200707280937.FAA00004@smc.vnet.net>

Daniel Lichtblau wrote:
> Peter Pein wrote:
> 
>>Dear group,
>>
>>I've written code, which looks for numbers for which a smaller natural
>>number exists which has the same sum of cubes of it's divisors:
>>
>>Block[{spa, nmax = 6*106, expo = 3},
>>   Reap[For[n = 1, n <= nmax, n++,
>>      (If[Head[#1] === spa, #1 = n, Sow[{n, #1}]] & )[
>>       spa[DivisorSigma[expo, n]]]]][[2,1]]]
>>
>>the name spa is an artefact; I tried this with SparseArrays, but the
>>allowed range of indices has not been sufficient. I now use spa as an
>>initially undefined function (Block[{spa..}]). For each n to test I look
>>wether spa[sigma(r,n)] has been defined. If not, the Head is still spa
>>and I set spa[sigma(r,n)] to n; else the remembered value together with
>>n will go to the result via the Sow-Reap mechanism.
>>
>> If you've got RAM (4GB or so) than I do (1.5 GB),
>>could you please run this code  with, say nmax=10 or 20 million? On my
>>machine it swapped heavily with nmax=6 million and I had to kill
>>MathKernel as I tried nmax=10^7. The lines above took ~181 seconds to
>>evaluate (nmax=10^7 has been stopped by me after 15 minutes). I do not
>>expect any runtimes of more than ~7-10 minutes. Would this be possible,
>>please?
>>
>> Alternatively any hints how to calculate these sequences more efficient
>>would be highly appreciated (AFAIK there exists no kind of "inverse
>>function" to sigma(r,n) w.r.t. n which could be calculated without this
>>brute-force method).
>>
>>Thank you for your attention and in advance for CPU-time,
>>
>>Peter
> 

Here is a way that removes excess storage, requiring only 8-10% or so of 
the previous memoization-based code I had used. The idea is to discard 
down values once they are known not to be needed.

duplicatedDivisorSumCubes[n_] := Module[
   {c, dsc, cdsc, jlo = 1, cinv, len = Ceiling[.064*n]},
   Off[Unset::"norep"];
   cinv = Table[0, {len}];
   Reap[Do[
     dsc = DivisorSigma[3, j];
     cdsc = c[dsc];
     cinv[[Mod[j, len, 1]]] = dsc;
     If[IntegerQ[cdsc],
       Sow[{j, cdsc, dsc}]];
     c[dsc] = j;
     While[jlo*1.064 < j, c[cinv[[Mod[jlo, len, 1]]]] =.; jlo++],
     {j, 1, n}]][[2, 1]]
   ]

The Off[...] is due to the fact that c[j] is not quite a 1-1 function. 
Indeed, the point of this exercise is to locate values for which it 
fails to be 1-1.

The constant 1.064 is just a hair over Zeta[3]^(1/3). I use this because 
it gives a bound on how much larger j2 can be than j1, such that 
DivisorSigma[3,j2]==DivisorSigma[3,j1]. This is not hard to show. It 
also turns out to be reasonably tight: the maximum quotient of such 
j2/j1 seen in this range is around 1.051 (a value oft repeated).

To go further than 10^8 will require a smarter method at least for 32 
bit versions of Mathematica. This run below gets us pretty close to out 
of memory on the machine I used.

In[4]:= InputFormTiming[duplicatedDivisorSumCubes[10^8]]]

Out[5]//InputForm=
{5226.374627, {{194315, 184926, 7401260364550416},
   {295301, 291741, 25751423829890304}, {590602, 583482, 
231762814469012736},
   {1181204, 1166964, 1879853939581992192}, {1476505, 1458705,
    3244679402566178304}, {1886920, 1880574, 7760807890757026560},
   {2067107, 2042187, 8858489797482264576}, {2362408, 2333928,
    15064582940485827840}, {2526095, 2404038, 16267970281281814368},
   {2953010, 2917410, 29202114623095604736}, {3248311, 3209151,
    34300896541413884928}, {3691985, 3513594, 50772646100815853760},
   {3838913, 3792633, 56601629578098888192}, {4134214, 4084374,
    79726408177340381184}, {4469245, 4253298, 90058536115849461888},
   {4724816, 4667856, 120542414947716513024},
   {5020117, 4959597, 126542496700080953856},
   {5610719, 5543079, 176654767473047485440},
   {5635135, 5362854, 180516740291384646240},
   {5906020, 5834820, 236861596387331016192},
   {6023765, 5732706, 220498348780685993472},
   {6496622, 6418302, 308708068872724964352},
   {6791923, 6710043, 313343325162105219072},
   {7382525, 7293525, 405610676744602178304},
   {7677826, 7585266, 509414666202889993728},
   {7966915, 7581966, 510109666845543771552},
   {8268428, 8168748, 646669755216205314048},
   {8355545, 7951818, 588459409064674475328},
   {8563729, 8460489, 628077227211024514560},
   {9132805, 8691522, 768428456089082390784},
   {9449632, 9335712, 964365071005561994496}, {10040234, 9919194,
    1138882470300728584704}, {10298695, 9801078, 1101884840553536833248},
   {10335535, 10210935, 1116169714482765336576},
   {10926137, 10794417, 1304412622679263458816},
   {11221438, 11086158, 1589892907257427368960},
   {11464585, 10910634, 1520070853671364438080},
   {11812040, 11669640, 1898137450501214307840},
   {11853215, 11280486, 1679952880066382524512},
   {12107341, 11961381, 1774839633203699532288},
   {12697943, 12544863, 2047444205866918290432},
   {12993244, 12836604, 2503965447523213599744},
   {13019105, 12390042, 2226032672283641317824},
   {13583846, 13420086, 2820089926458946971648},
   {13796365, 13129746, 2648999899596968491392},
   {14184995, 13499598, 2879223504496673731488},
   {14469749, 14295309, 3038487751960246639872},
   {14765050, 14587050, 3650496090701419604736},
   {15350885, 14609154, 3649117410137937104640},
   {15355652, 15170532, 4131918959201218838016},
   {15650953, 15462273, 3833820476946408678912},
   {16128145, 15348858, 4231951861325553263808},
   {16241555, 16045755, 4321912964218149500928},
   {16536856, 16337496, 5182216531527124776960},
   {17127458, 16920978, 5652695044899220631040},
   {17294035, 16458414, 5217666519197106767520},
   {17422759, 17212719, 5288827426182870635520},
   {18848555, 17937822, 6754937901955686372384},
   {18899264, 18671424, 7714946319468325846272},
   {19194565, 18963165, 7131805326840459912192},
   {19625815, 18677526, 7625533356117022705632},
   {19785167, 19546647, 7745101236773127392256},
   {20014445, 19047378, 8087564435634446974848},
   {20080468, 19838388, 9237602259105909631488},
   {20671070, 20421870, 10045527430344888029184},
   {20756120, 20686314, 10337396110488359377920},
   {20791705, 19787082, 9066869602030299818304},
   {20966371, 20713611, 9216743605803698485248},
   {21180335, 20156934, 9584854209903725232480},
   {21556973, 21297093, 10017767395456266281472},
   {21852274, 21588834, 11739713604113371129344},
   {21957595, 20896638, 10679263777489066145568},
   {22442876, 22172316, 12895798025532466437120},
   {22738177, 22464057, 11799508410246376415232},
   {23328779, 23047539, 12696482005089115484160},
   {23624080, 23339280, 15188344283412280641024},
   {24214682, 23922762, 15973556698833295790592},
   {24509983, 24214503, 14724355128845317143552},
   {24529960, 24447462, 17058255743883944378880},
   {24678005, 23485602, 15160623310579239327744},
   {25100585, 24797985, 15944354584210200185856},
   {25395886, 25089726, 18426997852802264613888},
   {25455265, 24225306, 16638714215462873806272},
   {25986488, 25673208, 20066024476727122682880},
   {26281789, 25964949, 18153981257357767610880},
   {26621155, 25334862, 19031260443428170383264},
   {26872391, 26548431, 19470960574866017538048},
   {27009785, 25704714, 19876972860243888217920},
   {27167692, 26840172, 22874062736833680992256},
   {28053595, 27715395, 22258500701603983165440},
   {28644197, 28298877, 23502654992521303312896},
   {28939498, 28590618, 27346389767642219758848},
   {28952935, 27553974, 24482999222914548607200},
   {29341565, 27923826, 25482184174649583868032},
   {29530100, 29174100, 29609579402355959016192},
   {29825401, 29465841, 26531743474783639991808},
   {30507455, 29033382, 28642093077211467575904},
   {30711304, 30341064, 33111953303187849592320},
   {31301906, 30924546, 34504384292517678110208},
   {31597207, 31216287, 31546627254264137573376},
   {31673345, 30142938, 32052993521255984991168},
   {32187809, 31799769, 33348866402422840389120},
   {32450605, 30882642, 34471103702520438705024},
   {32483110, 32091510, 38897216677963345508352},
   {32839235, 31252494, 35740738109236510716912},
   {33073712, 32674992, 41466590742014480480256},
   {33369013, 32966733, 37156677941301059860992},
   {33616495, 31992198, 38321639012219250830688},
   {33959615, 33550215, 39481258970425257603072},
   {34254916, 33841956, 45849637586404789562880},
   {34782385, 33101754, 42448744619220582901440},
   {34845518, 34425438, 47599446835645835719680},
   {35140819, 34717179, 43530618864827848126464},
   {35171015, 33471606, 43887564436609912872672},
   {35731421, 35300661, 45654519048045710729472},
   {35851480, 35730906, 53239142130593202201600},
   {36912625, 36467625, 50701360344499102178304},
   {37114165, 35320866, 51571034858860636234752},
   {37502795, 35690718, 53208090033854084548128},
   {37503227, 37051107, 52748804550366020468736},
   {37798528, 37342848, 61719596307170436660480},
   {38280055, 36430422, 56585403558364272175584},
   {38389130, 37926330, 64186247941564139209728},
   {38668685, 36800274, 58326372428876008329600},
   {38684431, 38218071, 57891569900585753299968},
   {39275033, 38801553, 60769240010728334991360},
   {39570334, 39093294, 69705911130958146530304},
   {40160936, 39676776, 74027360569547358005760},
   {40456237, 39968517, 66216026670683752751616},
   {41000465, 39019386, 69526936578881818475712},
   {41046839, 40551999, 69158538866029998228480},
   {41342140, 40843740, 81480389157241869570048},
   {41932742, 41427222, 82950692452233286367232},
   {42228043, 41718963, 75393370598027719071744},
   {42818645, 42302445, 79137730628589088834560},
   {43113946, 42594186, 90159906559106396533248},
   {43332245, 41238498, 82076780098386627660288},
   {43704548, 43177668, 95222121455586232493568},
   {43999849, 43469409, 85184422458085631116800},
   {44109505, 41978202, 86573164190016838186944},
   {44498135, 42348054, 88881661705282300239840},
   {44590451, 44052891, 88660916177968481937408},
   {44885752, 44344632, 103343038971732778982400},
   {45275395, 43087758, 93621043977201430024608},
   {45476354, 44928114, 106195575692217387737088},
   {46362257, 45803337, 99655280570749508107776},
   {46441285, 44197314, 101041414396013115198720},
   {46657558, 46095078, 114268338045802039357440},
   {46829915, 44567166, 103599304780522468069152},
   {47248160, 46678560, 121509998946700811306496},
   {47543461, 46970301, 107790103855764195360768},
   {47995805, 45676722, 111598276129593246564480},
   {48134063, 47553783, 111522927248449774267392},
   {48429364, 47845524, 129563293223870065857024},
   {48773065, 46416426, 117037995262247594912832},
   {49019966, 48429006, 132519196159607854291968},
   {49315267, 48720747, 119936329436456214829056},
   {49905869, 49304229, 124353805934507087248128},
   {49938955, 47525982, 125633389776535304131104},
   {50201170, 49595970, 143499191257891801672704},
   {50791772, 50179452, 149463427028285035201536},
   {51087073, 50471193, 133333610689651965046272},
   {51104845, 48635538, 134639643056179936042368},
   {51677675, 51054675, 139530072800143149336576},
   {51972976, 51346416, 160562496710358395347968},
   {52270735, 49745094, 144066347134613947985760},
   {52563578, 51929898, 163385831316219908497920},
   {52659365, 50114946, 147303673220589029044992},
   {52858879, 52221639, 147693171148523056143360},
   {53449481, 52805121, 152699299443901391021568},
   {53744782, 53096862, 175238645173794157842432},
   {53825255, 51224502, 157305899304970481336544},
   {54335384, 53680344, 183305845219831553157120},
   {54602515, 51964206, 164219475821579941325472},
   {54630685, 53972085, 164355990457587195810816},
   {54720680, 54536646, 189286104455563877798400},
   {54991145, 52334058, 167750957599483714118208},
   {55221287, 54555567, 168554605604507830536192},
   {56107190, 55430790, 200326506314435848488960},
   {56402491, 55722531, 179432625064425412313088},
   {56934295, 54183318, 186169512104892942863328},
   {56993093, 56306013, 185128479495663529093632},
   {57288394, 56597754, 211523894932691729816064},
   {57878996, 57181236, 221809605893098004710656},
   {58100185, 55292874, 197948662382637117229824},
   {58174297, 57472977, 196879266212023753053696},
   {58494520, 58297794, 231209988681433335275520},
   {58764899, 58056459, 202936670633833529702400},
   {59060200, 58348200, 237282245895592274307840},
   {59650802, 58931682, 238785691273052759926272},
   {59654705, 56772282, 214151353547503596928704},
   {59946103, 59223423, 216058566160592433008640},
   {60431965, 57511986, 222631628858081088976512},
   {60536705, 59806905, 223629793783666141068288},
   {60820595, 57881838, 226954453394162592247968},
   {61422608, 60682128, 264952228055080895626752},
   {61597855, 58621542, 235767252530398605385824},
   {61717909, 60973869, 235304150274099250606080},
   {62308511, 61557351, 241907124361169083235328},
   {62603812, 61849092, 279868894817087833560576},
   {63194414, 62432574, 283919645288377238160384},
   {63489715, 62724315, 257977969939231704594432},
   {64318265, 61210506, 268404427532228554711872},
   {64375618, 63599538, 300139797621805563502080},
   {64966220, 64183020, 315499646387924913567744},
   {65261521, 64474761, 278140407746777936575488},
   {65484155, 62320062, 283266617222388392165664},
   {65852123, 65058243, 285572165658388958748672},
   {66147424, 65349984, 331741584425913326106624},
   {66738026, 65933466, 334410101471709538748928},
   {67033327, 66225207, 301216567657828596673536},
   {67427305, 64169322, 309238898055857775480384},
   {67623929, 66808689, 309248591258914361832960},
   {67815935, 64539174, 314616846269509586056800},
   {67919230, 67100430, 355331330733827318427648},
   {68509832, 67683912, 367425177918449341017600},
   {68593195, 65278878, 325559076827751128482848},
   {68805133, 67975653, 325738464005536958218752},
   {69691036, 68850876, 386084402111349556392960},
   {69759085, 66388434, 342443586899920721604480},
   {69816040, 69581238, 393115962898406423370240},
   {70147715, 66758286, 348249587006756305490256},
   {70281638, 69434358, 391775569783450633138176},
   {70576939, 69726099, 351556378011756038983680},
   {71167541, 70309581, 360456121590213787826688},
   {71313605, 67867842, 365850694508682034439424},
   {71462842, 70601322, 410890671432411396565248},
   {72348745, 71476545, 382849456746991076623872},
   {72479495, 68977398, 384089279967066855269088},
   {72939347, 72060027, 388287178905758372997120},
   {73256755, 69717102, 396775795160463452435520},
   {73645385, 70086954, 402924170170502774015040},
   {73825250, 72935250, 456312243100491919604736},
   {74120551, 73226991, 407213754380860509508608},
   {74422645, 70826658, 415816780860010642065408},
   {74711153, 73810473, 417373309115924151803904},
   {75006454, 74102214, 474739240953294184218624},
   {75588535, 71936214, 435666827935048295869920},
   {75597056, 74685696, 493756796208787323174144},
   {75892357, 74977437, 437119964434312974936576},
   {76482959, 75560919, 448717942201666629832704},
   {76778260, 75852660, 520621788859353573590016},
   {77143055, 73415622, 463102589585441691141984},
   {77363720, 77103534, 534890401446755784568320},
   {77368862, 76436142, 521024129105271779699712},
   {77664163, 76727883, 468455687527410310920192},
   {77920315, 74155326, 477242164621169013280032},
   {78254765, 77311365, 483061380095247493542912},
   {78308945, 74525178, 484655370619947813651456},
   {78550066, 77603106, 546923160096555014922240},
   {79140668, 78186588, 565392390284438299634688},
   {79435969, 78478329, 501254297505436055293440},
   {79474835, 75634734, 506378913533584843358880},
   {80026571, 79061811, 512518021791477734043648},
   {80321872, 79353552, 592345427053078944999936},
   {80912474, 79937034, 595944240036153774764544},
   {81137560, 80864682, 617046313778309667732480},
   {81207775, 80228775, 540273421423810101500928},
   {81417985, 77483994, 544437156491950473984960},
   {81798377, 80812257, 547319062486515748455936},
   {81806615, 77853846, 552270665264311363380192},
   {82093678, 81103998, 622426849794269984056320},
   {82684280, 81687480, 652959282972417721896960},
   {82979581, 81979221, 571373673497406920544768},
   {83570183, 82562703, 583660862372143759537152},
   {83749765, 79703106, 592567049356917039804672},
   {83865484, 82854444, 672822283223669989423104},
   {84138395, 80072958, 600854581045080909919008},
   {84456086, 83437926, 678540335382249471645696},
   {84751387, 83729667, 610544833822072639107072},
   {84915655, 80812662, 617801557754727308551680},
   {85304285, 81182514, 626180080537812961480320},
   {85341989, 84313149, 621703312038921556184832},
   {85637290, 84604890, 712239575657301799511040},
   {86081545, 81922218, 643453053161476347736128},
   {86227892, 85188372, 731297019868307438547456},
   {86523193, 85480113, 647745083172493873362432},
   {87113795, 86063595, 666392255699041700075520},
   {87247435, 83031774, 669953576749684423341600},
   {87409096, 86355336, 763081384267369123407360},
   {87999698, 86938818, 766659802122770680051200},
   {88294999, 87230559, 688728628706307271520256},
   {88685240, 88386978, 805758118449957525565440},
   {88801955, 84511182, 706405849826587717401504},
   {88885601, 87814041, 704320806818219891908608},
   {89180902, 88105782, 797948245601716337436672},
   {89579215, 85250886, 725117627465119704527712},
   {89771504, 88689264, 826920966541335279344640},
   {89967845, 85620738, 734596169971147027584768},
   {90657407, 89564487, 745103130726226527230976},
   {90745105, 86360442, 753800338659211824786624},
   {90952708, 89856228, 861364113947985478311936},
   {91838611, 90731451, 774608803133428878870528},
   {92429213, 91314933, 789649334244057589166592},
   {92724514, 91606674, 896897525136745572969984},
   {93076885, 88579554, 813415092887307311331840},
   {93315116, 92190156, 926843186371505430343680},
   {93610417, 92481897, 820311966621089252384256},
   {94201019, 93065379, 836598866645084653393920},
   {94496320, 93357120, 972083236253009056630272},
   {94631405, 90058962, 854855223349088421742464},
   {95086922, 93940602, 970110934701877758246912},
   {95382223, 94232343, 868081527362555343452160},
   {95408665, 90798666, 876092903124834174841152},
   {95972825, 94815825, 891532267484635587912192},
   {96268126, 95107566, 1003706345236047968406528},
   {96858728, 95691048, 1038281185424164226388480},
   {96963185, 92278074, 919617702185936013624000},
   {97740445, 93017778, 941910505639252074027648},
   {97744631, 96566271, 933867453752432268346368},
   {98039932, 96858012, 1074877924405708151479296},
   {98630534, 97441494, 1079426964928105933461504},
   {98906335, 94127334, 976020709083876305347680},
   {98925835, 97733235, 975882755833414051424256},
   {99516437, 98316717, 985577909391129451977216},
   {99811738, 98608458, 1119184253410563785233152}}}


Daniel Lichtblau
Wolfram Research


  • Prev by Date: Re: Documentation Center (v6): do-it-yourself Mathematica
  • Next by Date: Re: Documentation Center (v6): do-it-yourself Mathematica Book
  • Previous by thread: Re: Cube codes just done in Mathematica
  • Next by thread: Integro-differential analog of Love's equation via power series