Anonymous user
Talk:Palindromic gapful numbers: Difference between revisions
m
→Nice Recursive Solution/Definition: added a rhetorical query.
m (→Nice Recursive Solution/Definition: added a rhetorical query.) |
|||
| (3 intermediate revisions by one other user not shown) | |||
Line 3:
If I let f<sub>1</sub> = 0..1..9 and f<sub>2</sub> = 0..11..99 then f<sub>3</sub> is xyx where x is 0..1..9 and y is f<sub>1</sub>. In general f<sub>n</sub> is (x<sup>n-1</sup>+x)+10*f<sub>n-2</sub>. For all palindromic numbers x=0 is invalid for outermost pair. Not a problem for this task as you will wish to choose x to be the ending for each set. Each set is then filtered to verify divisibility by 11x. F# can implement this and execute the entire task in less than 35 thousandths of a sec so sufficiently optimal. Obviously this implies that all palindromic gapful numbers are divisible by 11, but can this be used to improve on 35 thousandths of a sec?
--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 15:07, 3 December 2020 (UTC)
:Having calculated an outer 101, the 101 rem 11 == 2 determines permitted inners, in this case only 2, since 2*10 rem 11 is the needed 9. That idea needs generalising to d{0}d*10^k rem n11, ideally passing the outer remainder, needed inner length and trailing zeroes, then we don't actually have to perform any potentially expensive inner remainders at all, and maybe not even on the way in. A few small snippets from a quick experiment yields some clear patterns, both horizontal and vertical:
<pre style="font-size: 9px">i=6, j=0, k=3: 3r66=3, 30r66=30, 300r66=36, 3000r66=30, 30000r66=36, 300000r66=30, 3000000r66=36, 30000000r66=30, 300000000r66=36,
i=6, j=1, k=3: 33r66=33, 330r66=0, 3300r66=0, 33000r66=0, 330000r66=0, 3300000r66=0, 33000000r66=0, 330000000r66=0, 3300000000r66=0,
i=6, j=2, k=3: 303r66=39, 3030r66=60, 30300r66=6, 303000r66=60, 3030000r66=6, 30300000r66=60, 303000000r66=6, 3030000000r66=60, 30300000000r66=6,
i=6, j=3, k=3: 3003r66=33, 30030r66=0, 300300r66=0, 3003000r66=0, 30030000r66=0, 300300000r66=0, 3003000000r66=0, 30030000000r66=0, 300300000000r66=0,
i=6, j=4, k=3: 30003r66=39, 300030r66=60, 3000300r66=6, 30003000r66=60, 300030000r66=6, 3000300000r66=60, 30003000000r66=6, 300030000000r66=60, 3000300000000r66=6,
i=6, j=5, k=3: 300003r66=33, 3000030r66=0, 30000300r66=0, 300003000r66=0, 3000030000r66=0, 30000300000r66=0, 300003000000r66=0, 3000030000000r66=0, 30000300000000r66=0,
i=6, j=6, k=3: 3000003r66=39, 30000030r66=60, 300000300r66=6, 3000003000r66=60, 30000030000r66=6, 300000300000r66=60, 3000003000000r66=6, 30000030000000r66=60, 300000300000000r66=6,
i=6, j=7, k=3: 30000003r66=33, 300000030r66=0, 3000000300r66=0, 30000003000r66=0, 300000030000r66=0, 3000000300000r66=0, 30000003000000r66=0, 300000030000000r66=0, 3000000300000000r66=0,
i=6, j=8, k=3: 300000003r66=39, 3000000030r66=60, 30000000300r66=6, 300000003000r66=60, 3000000030000r66=6, 30000000300000r66=60, 300000003000000r66=6, 3000000030000000r66=60, 30000000300000000r66=6,
i=6, j=9, k=3: 3000000003r66=33, 30000000030r66=0, 300000000300r66=0, 3000000003000r66=0, 30000000030000r66=0, 300000000300000r66=0, 3000000003000000r66=0, 30000000030000000r66=0, 300000000300000000r66=0,
</pre>
:Obviously there is a fair bit of 30+36=66 and 60+6=66 going on there, however as well as the full dividend it can be say 22, in this case a third of it
<pre style="font-size: 9px">
i=6, j=8, k=1: 100000001r66=35, 1000000010r66=20, 10000000100r66=2, 100000001000r66=20, 1000000010000r66=2, 10000000100000r66=20, 100000001000000r66=2, 1000000010000000r66=20, 10000000100000000r66=2,
</pre>
:However, there are also some longer cycles:
<pre style="font-size: 9px">i=7, j=0, k=1: 1r77=1, 10r77=10, 100r77=23, 1000r77=76, 10000r77=67, 100000r77=54, 1000000r77=1, 10000000r77=10, 100000000r77=23,
i=7, j=1, k=1: 11r77=11, 110r77=33, 1100r77=22, 11000r77=66, 110000r77=44, 1100000r77=55, 11000000r77=11, 110000000r77=33, 1100000000r77=22,
i=7, j=2, k=1: 101r77=24, 1010r77=9, 10100r77=13, 101000r77=53, 1010000r77=68, 10100000r77=64, 101000000r77=24, 1010000000r77=9, 10100000000r77=13,
i=7, j=3, k=1: 1001r77=0, 10010r77=0, 100100r77=0, 1001000r77=0, 10010000r77=0, 100100000r77=0, 1001000000r77=0, 10010000000r77=0, 100100000000r77=0,
i=7, j=4, k=1: 10001r77=68, 100010r77=64, 1000100r77=24, 10001000r77=9, 100010000r77=13, 1000100000r77=53, 10001000000r77=68, 100010000000r77=64, 1000100000000r77=24,
i=7, j=5, k=1: 100001r77=55, 1000010r77=11, 10000100r77=33, 100001000r77=22, 1000010000r77=66, 10000100000r77=44, 100001000000r77=55, 1000010000000r77=11, 10000100000000r77=33,
i=7, j=6, k=1: 1000001r77=2, 10000010r77=20, 100000100r77=46, 1000001000r77=75, 10000010000r77=57, 100000100000r77=31, 1000001000000r77=2, 10000010000000r77=20, 100000100000000r77=46,
i=7, j=7, k=1: 10000001r77=11, 100000010r77=33, 1000000100r77=22, 10000001000r77=66, 100000010000r77=44, 1000000100000r77=55, 10000001000000r77=11, 100000010000000r77=33, 1000000100000000r77=22,
i=7, j=8, k=1: 100000001r77=24, 1000000010r77=9, 10000000100r77=13, 100000001000r77=53, 1000000010000r77=68, 10000000100000r77=64, 100000001000000r77=24, 1000000010000000r77=9, 10000000100000000r77=13,
i=7, j=9, k=1: 1000000001r77=0, 10000000010r77=0, 100000000100r77=0, 1000000001000r77=0, 10000000010000r77=0, 100000000100000r77=0, 1000000001000000r77=0, 10000000010000000r77=0, 100000000100000000r77=0,
</pre>
:If we have to, we could probably memoise that stuff in a pretty small cache, rather than repeating divisions all the way down.
:Yes, obviously you need to start hunting above the tens of millions before such optimisations would start to kick in. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 20:09, 4 December 2020 (UTC)
::Above is now embodied in 2nd Phix version, though it turned out far more important for accuracy on stupidly large numbers, than for speed. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 23:15, 10 December 2020 (UTC)
::: Does ''stupidly large'' numbers fit somewhere between:
:::::: gihugeic
::: and
:::::: ginormous numbers? -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 01:07, 11 December 2020 (UTC)
==Please clarify==
| |||