At first I thought this problem was an algorithms problem. I spent several days perfecting an algorithm to create all the palendromic compositions of numbers that contained a 2. But I realized that even if I made the world’s best algorithm, it still wouldn’t be fast enough because of the sheer number of compositions that I needed to sift through and count.
So I took a step back and thought about the issue from a combinatorics lens. I did a lot of reading and poking on the internet and discovered the “stars and bars” method. This was a real breakthrough. I was then able to very easily calculate the total number of compositions of a number that are palendromic.
From there I searched for a way to find either compositions that included a 2 or compositions that excluded 2s. In playing around on oeis.org I found https://oeis.org/A005251 which was the exact sequence I needed! I grabbed the generating function and that lead me to the solution.
modulo = 1000000
def solve(to=float('inf')):
last_no_2 = n = 0
while n < to:
n += 1
total = 1 << n // 2
if n % 2 == 0:
last_no_2 += no_2(n // 2)
total += no_2((n - 2) // 2)
total -= last_no_2 + 1
if total % modulo == 0 and total > modulo:
break
return n, total
_perms = {}
def no_2(n):
if n in _perms:
return _perms[n]
elif n < 0:
return 0
elif n < 3:
return 1
p = no_2(n - 1) + no_2(n - 2) + no_2(n - 4)
_perms[n] = p
return p
if __name__ == '__main__':
import sys
n = float(sys.argv[1])
a, _ = solve(n)
print(a)
import pytest
from problem import solve
_t_tests = (
(1, 0),
(2, 1),
(3, 0),
(4, 2),
(5, 1),
(6, 4),
(7, 3),
(8, 9),
(9, 7),
(10, 20),
(11, 16),
(12, 43),
(13, 36),
(14, 91),
(15, 79),
(16, 191),
(17, 170),
(18, 398),
(19, 361),
(20, 824),
(21, 759),
(22, 1697),
(23, 1583),
(24, 3480),
(25, 3280),
(26, 7111),
(27, 6760),
(28, 14487),
(29, 13871),
(30, 29439),
(42, 1999923),
(45, 3968274),
(50, 32632321),
(55, 130455888),
(60, 1058395038),
(70, 34104320267),
(80, 1095260678664),
(90, 35113623115748),
(100, 1124722424576767),
)
@pytest.mark.parametrize('to,expect', _t_tests)
def test_solve(to, expect):
n, actual = solve(to)
assert n == to
assert expect == actual