Talk:Palindromic gapful numbers

Nice Recursive Solution/Definition

If I let f₁ = 0..1..9 and f₂ = 0..11..99 then f₃ is xyx where x is 0..1..9 and y is f₁. In general f_n is (x^n-1+x)+10*f_n-2. 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? --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:

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,

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

i=6, j=8, k=1:  100000001r66=35,  1000000010r66=20,  10000000100r66=2,  100000001000r66=20,  1000000010000r66=2,  10000000100000r66=20,  100000001000000r66=2,  1000000010000000r66=20,  10000000100000000r66=2,

However, there are also some longer cycles:

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,

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. --Pete Lomax (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. --Pete Lomax (talk) 23:15, 10 December 2020 (UTC)

Does stupidly large numbers fit somewhere between:

gihugeic

and

ginormous numbers? -- Gerard Schildberger (talk) 01:07, 11 December 2020 (UTC)

Please clarify

I don't understand the second and third part of the requirements. What does this mean?

Show (nine sets, like above) of palindromic gapful numbers:

the last 15 palindromic gapful numbers (out of 100)
the last 10 palindromic gapful numbers (out of 1,000) {optional}

Thanks. --Paddy3118 (talk) 19:54, 12 November 2019 (UTC)

Is it:

The last fifteen of the first 100 binned-by-last digit gapful numbers >= 100

--Paddy3118 (talk) 19:59, 12 November 2019 (UTC)

Yes, that's my understanding and it must be correct as it's what Gerard's REXX entry does and he's the author of the task. --PureFox (talk) 20:38, 12 November 2019 (UTC)

Starting at 100 (which is the minimum that gapful numbers start at, as per the note on the task page that all positive integers below 100 are trivially gapful numbers), then ...

generate 100 palindromic gapful numbers, and then take (pick) the last 15 of those 100 numbers.
generate 1000 palindromic gapful numbers, and then take (pick) the last 10 of those 1000 numbers.

There is probably a better and cleaner (or more concise) way of expressing the above (two) sentences, but the (bottom/lower) limit of 100 kinda throws a monkey wrench into the works, er ... wording of the expression.

Another way of expressing the above would be:

generate the 86^th ──► 100^th palindromic gapful numbers, ignoring those below 100.
generate the 991^st ──► 1000^th palindromic gapful numbers, ignoring those below 100.

I had assumed that programmers would take/pick those (above) palindromic gapful numbers in increasing order, and it seemed unnecessary to state that.

I must admit, I never heard of that phrase binned by last, but once reading it, I knew what it meant.

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. -- 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

--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. -- Gerard Schildberger (talk) 20:52, 13 November 2019 (UTC)