Palindromic Sequences

Given an irrational number $\alpha$, let $S_\alpha(n)$ be the sequence $S_\alpha(n)=\lfloor {\alpha \cdot n} \rfloor – \lfloor {\alpha \cdot (n-1)} \rfloor$ for $n \ge 1$.
($\lfloor \cdots \rfloor$ is the floor-function.)

It can be proven that for any irrational $\alpha$ there exist infinitely many values of $n$ such that the subsequence $ \{S_\alpha(1),S_\alpha(2)…S_\alpha(n) \} $ is palindromic.

The first $20$ values of $n$ that give a palindromic subsequence for $\alpha = \sqrt{31}$ are:
$1$, $3$, $5$, $7$, $44$, $81$, $118$, $273$, $3158$, $9201$, $15244$, $21287$, $133765$, $246243$, $358721$, $829920$, $9600319$, $27971037$, $46341755$, $64712473$.

Let $H_g(\alpha)$ be the sum of the first $g$ values of $n$ for which the corresponding subsequence is palindromic.
So $H_{20}(\sqrt{31})=150243655$.

Let $T=\{2,3,5,6,7,8,10,\dots,1000\}$ be the set of positive integers, not exceeding $1000$, excluding perfect squares.
Calculate the sum of $H_{100}(\sqrt \beta)$ for $\beta \in T$. Give the last $15$ digits of your answer.

This problem is computationally intensive and requires a lot of steps to be solved manually. It seems it is designed for computer-assisted solutions.

At the heart of the problem is the creation of a floor sequence, which is actually creating a sequence of integers from non-integer rationals. In itself, this is not a big deal – but the requirement that subsequence needs to be palindromic, makes the job complicated.

Creating a palindromic checker is straightforward – we merely read the sequence forwards and backwards, then check if the two are the same.

The code below in Python should generate an answer:

“`python
from math import sqrt, floor
from itertools import count

def floor_sequence(alpha,n):
“Generates the floor sequence S for a given alpha and n”
return [floor(alpha * i) – floor(alpha * (i – 1)) for i in range(1, n+1)]

def is_palindrome(seq):
“Checks if a sequence is a palindrome”
return seq == seq[::-1]

def H(alpha, g):
“Generates the sum of the first g values of n for which the subsequence is palindromic”
n_values = []
for n in count(1):
seq = floor_sequence(alpha, n)
if is_palindrome(seq):
n_values.append(n)
if len(n_values) == g:
return sum(n_values)

T = [i for i in range(2, 1001) if int(sqrt(i))**2 != i]
answer = sum(H(sqrt(beta), 100) for beta in T)

answer % 10**15 # Return the last 15 digits
“`

This code generates the required sequences, checks if they are palindromes and stops once it has found the required number of them. It then runs this for all the required irrational square roots and returns the last 15 digits of the total sum.

Please note: This program will take a significant amount of time to execute due to its high computational complexity. For such high numbers, specially designed algorithms or mathematical insights not included in this code may be expected. Thus, using this type of brute-force approach may not be feasible in a reasonable time.

More Answers: