Pattern of palindromes(팔린드롬의 규칙)

A week ago I was just listing binary numbers, to see if there's any pattern in them(cause it's fun to do!). After I while, I noticed that there were the same number of palindromes in 1-digit and 2-digit numbers , another number of palindromes in 3-digit and 4-digit numbers, and so on. Palindromes are numbers that have the same digits starting from the front and the back. In other words, the left part's number sequence is in symmetry with the right. I also counted the number of palindromes for the base-3 numbers, and they also had that repeating pattern. So I thought about how many palindromes would there be for a certain digit and a certain base number.

 

{The number of k-digit palindromes in base-n numbers}

Let's start with decimal numbers: there will be 9 1-digit palindromes(not counting 0), for 2-digit numbers also 9, for 3,4-digit numbers 90, for 5,6-digit numbers 900, ... etc. How to calculate this I will explain. For a 3-digit palindrome, the first and last digit should be the same, and the one in middle can be of any number. In this case of decimal numbers, there can be total 9 cases, not counting 0 since it then becomes not a 3-digit number but a 2-digit one, of choosing the first and last number. Since the number in the middle has 10 cases, the total case would be 9X10=90. For an another example, 4-digit decimal palindromes have a total of 90 cases because the outer two numbers(first and last) have 9 cases, and the ones inside(second and third) have 10 cases. In conclusion, of base-n numbers, there are n-1 cases of 1-digit numbers, n-1 cases for 2-digit numbers, n(n-1) cases for 3,4 digit numbers, (n^2)(n-1) cases for 5,6-digit numbers, and so on.

digits	number of palindromes
1	(n^0)*(n-1)
2	(n^0)*(n-1)
3	(n^1)*(n-1)
4	(n^1)*(n-1)
5	(n^2)*(n-1)
6	(n^2)*(n-1)
7	(n^3)*(n-1)
8	(n^3)*(n-1)

I then wanted to figure out the general term of these numbers. So made a graph of them: x-axis as the number of digits(k), and y-axis the number of times n is powered(higlighted part, shown as w in graph).

Without the connecting lines, the graph seems simmilar to a Gauss graph. So I came to the conclusion that w=[(k-1)/2], where [ ] represents the biggest integer lower than the number in it. So when the number of k-digit palindromes in base-n numbers is x, x=(n^w)*(n-1)=(n^[(k-1)/2])*(n-1).

{The sum of the number of Palindromes up to k-digits in base-n numbers}

Then I wanted to calculate how many palindromes there would be up to a certain-digit(S_k). Since the pattern is repeated as n^0*(n-1), n^0*(n-1), n^1*(n-1), ....... , the sum of the cases of palindromes would be in different forms of equations when k is and even number and when it is not. When k is an even number, 

and when k is an odd number,

I wanted to combine those two equations into one; and what I came up with was using the gcd(greatest common diveder) of 2 and k. When k is even, gcd(2,k)(or just (2,k)) will be 2. When k is odd, gcd(2,k) will be 1. By defining another function r(w) and when w<1 r(w)=0, 

and in conclusion, 

 

 

 

 

 

cover image: https://m.blog.naver.com/PostList.nhn?blogId=wkdlkh86