Talk:Klarner-Rado sequence

From Rosetta Code
Revision as of 11:48, 22 August 2022 by Nigel Galloway (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Latest comment: 1 year ago by Nigel Galloway

Is there an authoritative source for the value of the 1 millionth item in the sequence. My computer is telling me it is 52,102,239. It is not often wrong.--Nigel Galloway (talk) 10:53, 19 August 2022 (UTC)Reply[reply]

I can't find any independent confirmation of the value of the 1 millionth term but, FWIW, I'm as sure as I can be that it's 54,381,285. I just tried running the Wren example to a limit of 1.2 million to make sure there was nothing unexpected going on here but still got the same answer for the millionth.
Your figure of 52,102,239 is the 963,815th element. --PureFox (talk) 12:45, 19 August 2022 (UTC)Reply[reply]
The other samples that go to the millionth element also show it as 54,381,285. --Tigerofdarkness (talk) 13:24, 19 August 2022 (UTC)Reply[reply]
My suspicion (though I haven't confirmed it) is that you are accumulating the x2 and x3 terms off of the same indexer so, when you reach 1e6th, you have excess x3 elements and a shortage of x2. The reason the earlier figures match is you have accumulated enough terms past it to have filled in any "gaps". I have also failed to find a 3rd party trusted source, but we now have at least 6 different implementations by at least 4 different authors that all agree on 54,381,285. Still not authoritative but circumstantial evidence is getting pretty convincing. --Thundergnat (talk) 15:02, 19 August 2022 (UTC)Reply[reply]
Nothing so exciting, it just need 64bit integers.--Nigel Galloway (talk) 11:48, 22 August 2022 (UTC)Reply[reply]

BTW, I just used a "bit-vector" as suggested by the Julia sample and it would seem that you need around 1.1 billion bits (137 500 000 bytes) to find the 10 millionth element, which I think is 1,031,926,801.
The final element below 1.1 billion is element 10,543,878 which appears to be 1,099,640,002. --Tigerofdarkness (talk) 13:24, 19 August 2022 (UTC)Reply[reply]