# Does this “almost all integers in order” sequence have a closed form?

Can you help me define a formula for the following sequence (first $130$ terms) :

0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 10, 11, 12, 13, 12, 15, 15, 17, 18, 18, 20, 21, 22, 23, 22, 25, 26, 27, 28, 28, 30, 31, 32, 33, 32, 35, 36, 37, 38, 38, 40, 41, 42, 43, 42, 45, 46, 47, 48, 48, 49, 50, 52, 53, 52, 55, 55, 57, 58, 57, 60, 61, 61, 63, 61, 65, 66, 67, 67, 68, 70, 71, 72, 73, 72, 75, 76, 77, 78, 78, 79, 81, 82, 83, 82, 85, 85, 87, 88, 88, 90, 91, 91, 93, 91, 95, 96, 97, 97, 98, 99, 101, 102, 102, 102, 105, 106, 107, 108, 107, 109, 111, 112, 113, 111, 115, 114, 117, 117, 117, 120, 121, 120, 123, 119, 125, 126, 127, 127, 128


How it was obtained:

Generate a set of all pairs of form $(x,y)$ by iterating $x,y$ both from $0$ to $N-1$ ,
You now have a set of $N^2$ such pairs.

Replace each pair with the number of 3-digit palindromes of form $(x+Nk)_y$ ,
You now have a set of $N^2$ nonnegative integers. ($k$ is any nonnegative integer)

• Note, if $y<2$, we set the value to $0$, since $2$ is the smallest integer number base

Count the number of distinct nonnegative integers in your set, to get the $f(N)$, where $f(1)=0$

My attempt on finding patterns

The sequence almost looks like a sequence of all nonnegative integers in order. It starts counting nicely, but at some places we see irregularities.

I tried to subtract $0,1,2,3,4\dots N-1$ from the first $130$ terms so far. We get:

0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, -2, 0, -1, 0, 0, -1, 0, 0, 0, 0, -2, 0, 0, 0, 0, -1, 0, 0, 0, 0, -2, 0, 0, 0, 0, -1, 0, 0, 0, 0, -2, 0, 0, 0, 0, -1, -1, -1, 0, 0, -2, 0, -1, 0, 0, -2, 0, 0, -1, 0, -3, 0, 0, 0, -1, -1, 0, 0, 0, 0, -2, 0, 0, 0, 0, -1, -1, 0, 0, 0, -2, 0, -1, 0, 0, -1, 0, 0, -1, 0, -3, 0, 0, 0, -1, -1, -1, 0, 0, -1, -2, 0, 0, 0, 0, -2, -1, 0, 0, 0, -3, 0, -2, 0, -1, -2


Now we are left with negative numbers at the places of irregularities. My goal was to find the patterns of all irregularities so I can work a formula for the sequence.

We have $65$ irregularities. I found three patterns so far:

• one is subtracted at every $5$ terms, starting at $10$th term
• one is subtracted at every $10$ terms, starting at $15$th term
• one is subtracted at every $30$ terms, starting at $51$th term (confirmed up to $231$th term)

By excluding these, we are left with $25$ irregularities among our first $130$ terms, located at the following places in the sequence:

17 52 57 60 63 65 69 87 93 95 99 101 104 110 115 117 117 119 120 123 123 125 125 125 129


Pattern starting at $17$th place occurs at least every $70$ terms or more, if it exists. I'm not sure about any other patterns that could start at any of these places.

Without a more general approach, it would be hard to find all the irregularities, since the patterns don't seem obvious. Also, it gets harder to compute big terms very quickly. it is sufficient to check $k$ values in range:

$$0\le k \le N^2-3N+2$$

Since beyond that bound, bigger $k$ will not produce any more 3-digit palindromes of form $(x+Nk)_y$ for values $0\le x,y \lt N$ .

This came up from my previous question related to patterns generated when plotting palindromes in a certain way.

This sequence is, in other words, number of distinct colors on a graph of size $N\times N$ where each pixel $(x,y)$ is colored based on how much numbers of form $(x+Nk)$ that make a 3-digit palindrome in number base $y$ exist, where $k$ is some nonnegative integer.

For example, we can plot $N=130$, which consists of $128$ distinct colors:

$\hspace{7cm}$

• What does the $y$ in $(x + Nk)_y$ mean? – orlp May 5 '17 at 22:17
• @orlp That's the number base in which the number is represented to be checked if it's a palindrome. $y=2$ would mean you write down $x+Nk$ in binary and check how many $k$ exist such that it is a 3-digit palindrome. – Vepir May 5 '17 at 22:18