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