Re: Re: Faster alternative to AppendTo?
- To: mathgroup at smc.vnet.net
- Subject: [mg102972] Re: [mg102911] Re: [mg102886] Faster alternative to AppendTo?
- From: DrMajorBob <btreat1 at austin.rr.com>
- Date: Thu, 3 Sep 2009 05:41:35 -0400 (EDT)
- References: <200909010753.DAA18801@smc.vnet.net>
- Reply-to: drmajorbob at yahoo.com
Sorry... I meant to say, Collatz going to 10^5 took 8 or 9 times as long
as my code going to 10^6.
Clear[g, h]
g[1] = 1;
g[n_] := Which[
ListQ@n, n,
ListQ@h@n, Rest@h@n,
EvenQ@n, n/2,
True, 3 n + 1
]
AbsoluteTiming[
Table[h[m] = Flatten@Most@FixedPointList[g, m], {m, 1, 1000000}];]
{54.366878, Null}
Bobby
On Wed, 02 Sep 2009 19:09:22 -0500, DrMajorBob <btreat1 at austin.rr.com>
wrote:
> Unfortunately, Collatz raises $RecursionLimit and $IterationLimit errors.
>
> 10^6 is fine, but some number in the following range is not, since it
> throws a $RecursionLimit error:
>
> AbsoluteTiming[Table[Collatz@m, {m, 6*10^3, 7*10^3}];]
>
> The following code lists 761 failures up to 10^6, and it takes eight or
> nine times as long as the code I posted a few minutes ago:
>
> Off[$RecursionLimit::"reclim", $IterationLimit::"itlim"]
> Reap@AbsoluteTiming[Table[! ListQ@Collatz@m && Sow@m, {m, 1, 10^5}];]
>
> {{450.227054,
> Null}, {{6171, 6943, 7963, 9257, 10415, 10617, 10971, 11945, 12135,
> 12342, 12343, 12399, 12583, 13255, 13886, 13887, 14695, 15039,
> 15623, 15926, 15927, 16457, 16777, 17647, 17673, 18514, 18515,
> 18599, 18875, 19593, 19883, 20830, 20831, 20895, 21234, 21235,
> 21351, 21942, 21943, 22043, 22369, 22559, 23435, 23457, 23529,
> 23655, 23890, 23891, 24091, 24235, 24270, 24271, 24684, 24685,
> 24686, 24798, 24799, 25166, 25167, 26471, 26510, 26511, 26623,
> 27135, 27772, 27773, 27774, 27807, 27899, 28313, 29257, 29390,
> 29391, 29825, 30078, 30079, 30715, 31231, 31246, 31247, 31343,
> 31387, 31419, 31687, 31852, 31853, 31854, 32027, 32121, 32313,
> 32361, 32415, 32913, 32914, 32915, 33019, 33065, 33554, 33555,
> 33839, 34239, 34719, 35294, 35295, 35346, 35347, 35497, 35655,
> 37028, 37029, 37030, 37147, 37198, 37199, 37375, 37503, 37750,
> 37751, 37755, 39009, 39015, 39186, 39187, 39707, 39766, 39767,
> 39935, 40105, 40111, 40703, 40953, 40959, 41641, 41660, 41661,
> 41662, 41707, 41711, 41790, 41791, 41849, 42249, 42468, 42469,
> 42470, 42475, 42702, 42703, 43147, 43884, 43885, 43886, 44025,
> 44086, 44087, 44671, 44738, 44739, 45055, 45118, 45119, 45127,
> 46073, 46443, 46639, 46699, 46847, 46870, 46871, 46873, 46914,
> 46915, 46921, 47015, 47058, 47059, 47081, 47129, 47310, 47311,
> 47329, 47531, 47780, 47781, 47782, 47785, 47995, 48041, 48182,
> 48183, 48470, 48471, 48475, 48540, 48541, 48542, 48623, 48927,
> 49368, 49370, 49372, 49373, 49435, 49529, 49575, 49596, 49597,
> 49598, 49833, 50332, 50333, 50334, 50759, 50815, 51067, 51359,
> 52011, 52079, 52249, 52507, 52527, 52942, 52943, 53020, 53021,
> 53022, 53246, 53247, 53473, 53481, 53483, 53499, 54270, 54271,
> 54511, 55275, 55521, 55544, 55546, 55548, 55549, 55609, 55614,
> 55615, 55721, 55798, 55799, 56063, 56071, 56095, 56255, 56487,
> 56625, 56626, 56627, 56633, 56863, 56937, 57115, 57451, 57529,
> 57531, 57627, 58513, 58514, 58515, 58523, 58780, 58781, 58782,
> 59007, 59071, 59561, 59650, 59651, 59655, 59903, 60073, 60156,
> 60157, 60158, 60159, 60167, 60169, 60187, 60231, 60523, 60607,
> 60975, 61055, 61430, 61431, 61439, 61551, 61723, 61999, 62185,
> 62265, 62462, 62463, 62492, 62493, 62494, 62497, 62553, 62561,
> 62567, 62575, 62686, 62687, 62745, 62774, 62775, 62838, 62839,
> 63081, 63105, 63374, 63375, 63387, 63579, 63704, 63706, 63708,
> 63709, 63713, 63993, 64054, 64055, 64242, 64243, 64255, 64626,
> 64627, 64633, 64721, 64722, 64723, 64830, 64831, 64839, 65511,
> 65826, 65827, 65828, 65829, 65830, 65835, 65839, 65913, 66038,
> 66039, 66129, 66130, 66131, 66495, 67007, 67108, 67109, 67110,
> 67111, 67583, 67678, 67679, 67689, 67691, 67711, 67753, 68089,
> 68187, 68478, 68479, 69110, 69111, 69121, 69231, 69375, 69438,
> 69439, 69535, 69665, 69959, 70009, 70049, 70057, 70271, 70306,
> 70307, 70308, 70309, 70310, 70335, 70372, 70373, 70374, 70380,
> 70381, 70382, 70523, 70588, 70589, 70590, 70622, 70623, 70692,
> 70693, 70694, 70966, 70967, 70994, 70995, 71297, 71310, 71311,
> 71449, 71451, 71527, 71672, 71674, 71676, 71677, 71678, 71679,
> 71993, 72062, 72063, 72273, 72274, 72275, 72361, 72681, 72706,
> 72707, 72711, 72713, 72807, 72812, 72813, 72814, 72935, 72943,
> 73063, 73391, 73755, 74056, 74058, 74060, 74061, 74065, 74145,
> 74153, 74294, 74295, 74363, 74396, 74397, 74398, 74431, 74475,
> 74750, 74751, 74761, 74779, 74791, 74793, 75006, 75007, 75500,
> 75501, 75502, 75510, 75511, 75817, 75867, 75915, 76139, 76153,
> 76223, 76231, 76601, 76705, 76711, 77031, 77039, 78017, 78018,
> 78019, 78030, 78031, 78111, 78119, 78267, 78372, 78373, 78374,
> 78375, 78463, 78761, 78791, 79131, 79263, 79414, 79415, 79532,
> 79533, 79534, 79551, 79870, 79871, 80097, 80209, 80210, 80211,
> 80222, 80223, 80225, 80249, 80299, 80697, 80809, 81007, 81159,
> 81406, 81407, 81767, 81906, 81907, 81918, 81919, 82297, 82411,
> 82665, 82913, 82975, 83282, 83283, 83320, 83322, 83324, 83325,
> 83329, 83391, 83403, 83414, 83415, 83422, 83423, 83433, 83503,
> 83580, 83581, 83582, 83659, 83698, 83699, 83785, 84095, 84107,
> 84127, 84143, 84383, 84498, 84499, 84679, 84731, 84936, 84938,
> 84940, 84941, 84945, 84950, 84951, 85295, 85351, 85404, 85405,
> 85406, 85657, 85673, 85791, 86169, 86175, 86177, 86294, 86295,
> 86297, 86441, 87087, 87768, 87769, 87770, 87772, 87773, 87785,
> 87999, 88050, 88051, 88059, 88135, 88172, 88173, 88174, 88511,
> 88607, 89023, 89119, 89263, 89342, 89343, 89476, 89477, 89478,
> 89481, 89483, 89855, 90110, 90111, 90236, 90237, 90238, 90239,
> 90251, 90254, 90255, 90281, 90337, 90347, 90785, 90911, 91305,
> 91463, 91583, 92146, 92147, 92159, 92161, 92199, 92319, 92327,
> 92347, 92463, 92585, 92713, 92886, 92887, 92999, 93278, 93279,
> 93345, 93398, 93399, 93409, 93694, 93695, 93723, 93740, 93741,
> 93742, 93745, 93746, 93747, 93828, 93829, 93830, 93835, 93841,
> 93842, 93843, 93851, 93863, 94030, 94031, 94116, 94117, 94118,
> 94162, 94163, 94183, 94257, 94258, 94259, 94620, 94621, 94622,
> 94658, 94659, 94959, 95062, 95063, 95081, 95265, 95323, 95369,
> 95560, 95562, 95564, 95565, 95569, 95570, 95571, 95775, 95990,
> 95991, 96082, 96083, 96364, 96365, 96366, 96383, 96415, 96481,
> 96940, 96941, 96942, 96950, 96951, 97080, 97082, 97083, 97084,
> 97085, 97215, 97246, 97247, 97257, 97259, 97279, 97417, 97531,
> 97854, 97855, 98267, 98395, 98736, 98740, 98741, 98744, 98746,
> 98753, 98759, 98870, 98871, 98971, 99007, 99058, 99059, 99067,
> 99150, 99151, 99192, 99194, 99196, 99197, 99241, 99666, 99667,
> 99681, 99705, 99721, 99743, 99775}}}
>
> Bobby
>
> On Wed, 02 Sep 2009 03:01:45 -0500, Murray Eisenberg
> <murray at math.umass.edu> wrote:
>
>> There's a package Collatz.m that's long been distributed with
>> Mathematica. For Mathematica 7, it's in:
>>
>> $InstallationDirectory\Documentation\English\System\ExampleData
>>
>> You can copy the definitions from that .m file and try it directly
>> without having to load the package:
>>
>> Collatz[1] := {1}
>> Collatz[n_Integer]:= Prepend[Collatz[3 n + 1], n] /; OddQ[n] && n >
>> 0
>> Collatz[n_Integer] := Prepend[Collatz[n/2], n] /; EvenQ[n] && n > 0
>>
>> Collatz[1000000];//Timing
>> {1.0842*10^-19, Null} (* on my PC *)
>>
>>
>> Dem_z wrote:
>>> Hey, sorry I'm really new. I only started using mathematica recently,
>>> so I'm not that savvy.
>>>
>>> Anyways, I wrote some code to calculate (and store) the orbits around
>>> numbers in the Collatz conjecture.
>>>
>>> "Take any whole number n greater than 0. If n is even, we halve it
>>> (n/2), else we do "triple plus one" and get 3n+1. The conjecture is
>>> that for all numbers this process converges to 1. "
>>> http://en.wikipedia.org/wiki/Collatz_conjecture
>>>
>>>
>>> (*If there's no remainder, divides by 2, else multiply by 3 add 1*)
>>> g[n_] := If[Mod[n, 2] == 0, n/2, 3 n + 1]
>>>
>>> (*creates an empty list a. Loops and appends the k's orbit into
>>> variable "orbit", which then appends to variable "a" after the While
>>> loop is completed. New m, sets new k, which restarts the While loop
>>> again.*)
>>> a = {};
>>> Do[
>>> k = m;
>>> orbit = {k};
>>> While[k > 1, AppendTo[orbit, k = g[k]]];
>>> AppendTo[a, orbit];
>>> , {m, 2,1000000}];
>>>
>>> Anyways it seems that the AppendTo function gets exponentially slower,
>>> as you throw more data into it. Is there a way to make this more
>>> efficient? To calculate a million points takes days with this method.
>>>
>>
>
>
>
--
DrMajorBob at yahoo.com
- References:
- Faster alternative to AppendTo?
- From: Dem_z <dem_z@hotmail.com>
- Faster alternative to AppendTo?