Anonymous user
Talk:Palindromic gapful numbers: Difference between revisions
m
→Nice Recursive Solution/Definition: added a rhetorical query.
m (→Please clarify: added a comment.) |
m (→Nice Recursive Solution/Definition: added a rhetorical query.) |
||
| (8 intermediate revisions by 4 users not shown) | |||
Line 1:
==Nice Recursive Solution/Definition==
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==
I don't understand the second and third part of the requirements.
Line 41 ⟶ 84:
I hope the parenthetic phrase '''(nine sets)''' was clear enough; If it wasn't for the output, I don't know how I would've expressed it. I assumed the output from the REXX example would make that clear enough. I had toyed with expanding that parenthesized expression, but it just got too overly wordy and inelegant, and even somewhat ugly. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 00:12, 13 November 2019 (UTC)
:Hi Gerard, as you saw above, I did eventually work it out.
:Having looked again at my wording I think it might be better with an extra hyphen tieing in the word "digit"?
::''The last fifteen of the first 100 binned-by-last-digit gapful numbers >= 100''
:--[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 20:16, 13 November 2019 (UTC)
:P.S. I enjoyed the task.
== optimizations ==
(Referencing Paddy3118's comment above.)
I thought it was a pretty simple task, nothing much complicated, but enough computation so that it required just a hint of heavy lifting (at least, for the solution I entered). I thought I hit on a clever method to limit the calculation (to ten) entries per ending decimal digit without computing extra entries or excessive limit checking.
It was interesting to note some of the optimizations for this task, ... which to do first ... create palindromes and then filter the gapful numbers, or vice-versa. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 20:52, 13 November 2019 (UTC)
| |||