Find least binary palindrome greater than a natural number

I am looking for an efficient way to generate the least binary number, b, that yields a natural number greater than a given natural number, d.

A small example would be d = 15, binary = 1111, and for which the least largest b = 10001 (decimal value 17).

Assume the natural number of interest, d, is 1 quadrillion (10^15) for which the binary representation, b, is:

'11100011010111111010100100110001101000000000000000'

I have tried one standard approach from the literature, which is to form the sum b + reverse(b) and check to see if the

result is a palindrome that yields a natural number that is just above d. So far, after many cycles, that hasn't produced anything.

There is no guarantee this method will always work, for example, it fails for the number 196.

There is a wealth of tantalizing clues in the "OEIS," the Online Encyclopedia of Integer Sequences"

(for example: https://oeis.org/A006995) but nothing is given there in terms of MATLAB code.

[DGM]

While it's not ready-to-use code, there are formulae given. Seems to me you'd have to implement A006995 and A206916. With that, A206914(n) = A006995(A206916(n)). In other words, in order to get the least palindrome larger than n (A206914(n)), you'd use A206916 to get the index into the list of all binary palindromes (A006995).

Attached is a list of the first 160E3 members of this sequence.

aa = readmatrix('b.txt');
daa = diff(aa,1,2); % distance to next palindrome
n = aa(:,1); % the argument

% plot the error (distance to next palindrome)
plot(n,daa); hold on 

% just visually outline the boundary
sf = sqrt(9/2); % shape factor
plot(n,sf*sqrt(n)) % upper curve
plot(n,sf/2*sqrt(n)) % lower curve

% the boundary is found at the largest odd power of 2 < n
% the next palindrome should occur within [n n+nc]
p = floor((max(log2(n),1) + 1)/2)*2 - 1;
nc = 3*2.^((p - 1)/2);
plot(n,nc,'g')

From observation, it seems that the next palindrome occurs roughly within the interval [n+1 n+3*2.^((floor((max(log2(n),1) + 1)/2)*2 - 1 - 1)/2]. There's probably an actual formula for that.

Idk if any of this is useful information. I was just bored enough to poke at it.

[Ken Bannister]

Wow, thanks! That looks like a good approach and I will try it out and see what happens. KB 3/10/2025

[Image Analyst]

@Ken Bannister did you scroll down and see the other replies by other people?

Plus your link to oeis.org is broken, and you never answered my question if it's your homework (maybe because you didn't scroll down and only saw this one comment above.).

[DGM]

Fixed the OEIS link. I noticed that yesterday, but forgot about it.

[Sam Chak]

Hi @DGM, Thank you for the link. Are we permitted to submit @Voss–@Walter Roberson's heuristic solution in MATLAB for the binary palindromes problem to OEIS? I noticed that there are versions available in Maple, Mathematica, and Python.

[Ken Bannister]

Thank you, I have looked at the replies & suggestions following. I do have a question about your reply you have:

% the boundary is found at the largest odd power of 2 < n

% the next palindrome should occur within [n n+nc]

p = floor((max(log2(n),1) + 1)/2)*2 - 1;

nc = 3*2.^((p - 1)/2);

plot(n,nc,'g')

I realize that "n" here may have been picked from the file "b.txt" but since I am searching for the very next few binary palindromes occurring after 10^15 (1 quadrillion), could I start with

n = 10^15 (or its binary equivalent '11100011010111111010100100110001101000000000000000' ) ? Once I bracket the rascal, then perhaps I could find it (and its neighbors, as needed) by doing a brute-force search using a very nice routine that appeared in the MATLAB File Exchange. Can't seem to find the author of that routine now, unfortunately. What it does is, starting with 1, find the first n binary palindromes. I don't know if it be run using

other starting values. Thanks, Ken Bannister

[Ken Bannister]

I hope, too , that MATLAB-based solutions like the great work presented here can be submitted to OEIS for consideration for inclusion! They have Mathematica, Maple, Python, and other language-based solutions, but somehow

MATLAB solutions don't appear. - Ken Bannister

Answer 1

[Voss]

Based on / inspired by @Walter Roberson's answer.

function out = get_next_binary_palindrome(d)

d_input = isnumeric(d);

if d_input
    assert(isscalar(d));
    b = dec2bin(d);
else % char assumed
    assert(isrow(d));
    b = d;
    d = bin2dec(b);
end

n = numel(b);
m = rem(n,2);
idx = 1:(n+m)/2;

b_tmp = b(idx([1:end end-m:-1:1]));
d_tmp = bin2dec(b_tmp);

if d_tmp > d
    if d_input
        out = d_tmp;
    else
        out = b_tmp;
    end
else
    b_tmp = dec2bin(bin2dec(b(idx))+1);
    if numel(b_tmp) > (n+m)/2
        out = b_tmp([1:end-m end-1:-1:1]);
    else
        out = b_tmp([1:end end-m:-1:1]);
    end
    if d_input
        out = bin2dec(out);
    end
end

end

Examples:

get_next_binary_palindrome(15)

ans = 17

get_next_binary_palindrome('1111')

ans = '10001'

for d = 0:100
    result = get_next_binary_palindrome(d);
    fprintf('%d -> %d (%s)\n',d,result,dec2bin(result));
end

0 -> 1 (1)
1 -> 3 (11)
2 -> 3 (11)
3 -> 5 (101)
4 -> 5 (101)
5 -> 7 (111)
6 -> 7 (111)
7 -> 9 (1001)
8 -> 9 (1001)
9 -> 15 (1111)
10 -> 15 (1111)
11 -> 15 (1111)
12 -> 15 (1111)
13 -> 15 (1111)
14 -> 15 (1111)
15 -> 17 (10001)
16 -> 17 (10001)
17 -> 21 (10101)
18 -> 21 (10101)
19 -> 21 (10101)
20 -> 21 (10101)
21 -> 27 (11011)
22 -> 27 (11011)
23 -> 27 (11011)
24 -> 27 (11011)
25 -> 27 (11011)
26 -> 27 (11011)
27 -> 31 (11111)
28 -> 31 (11111)
29 -> 31 (11111)
30 -> 31 (11111)
31 -> 33 (100001)
32 -> 33 (100001)
33 -> 45 (101101)
34 -> 45 (101101)
35 -> 45 (101101)
36 -> 45 (101101)
37 -> 45 (101101)
38 -> 45 (101101)
39 -> 45 (101101)
40 -> 45 (101101)
41 -> 45 (101101)
42 -> 45 (101101)
43 -> 45 (101101)
44 -> 45 (101101)
45 -> 51 (110011)
46 -> 51 (110011)
47 -> 51 (110011)
48 -> 51 (110011)
49 -> 51 (110011)
50 -> 51 (110011)
51 -> 63 (111111)
52 -> 63 (111111)
53 -> 63 (111111)
54 -> 63 (111111)
55 -> 63 (111111)
56 -> 63 (111111)
57 -> 63 (111111)
58 -> 63 (111111)
59 -> 63 (111111)
60 -> 63 (111111)
61 -> 63 (111111)
62 -> 63 (111111)
63 -> 65 (1000001)
64 -> 65 (1000001)
65 -> 73 (1001001)
66 -> 73 (1001001)
67 -> 73 (1001001)
68 -> 73 (1001001)
69 -> 73 (1001001)
70 -> 73 (1001001)
71 -> 73 (1001001)
72 -> 73 (1001001)
73 -> 85 (1010101)
74 -> 85 (1010101)
75 -> 85 (1010101)
76 -> 85 (1010101)
77 -> 85 (1010101)
78 -> 85 (1010101)
79 -> 85 (1010101)
80 -> 85 (1010101)
81 -> 85 (1010101)
82 -> 85 (1010101)
83 -> 85 (1010101)
84 -> 85 (1010101)
85 -> 93 (1011101)
86 -> 93 (1011101)
87 -> 93 (1011101)
88 -> 93 (1011101)
89 -> 93 (1011101)
90 -> 93 (1011101)
91 -> 93 (1011101)
92 -> 93 (1011101)
93 -> 99 (1100011)
94 -> 99 (1100011)
95 -> 99 (1100011)
96 -> 99 (1100011)
97 -> 99 (1100011)
98 -> 99 (1100011)
99 -> 107 (1101011)
100 -> 107 (1101011)

d = 1e15;
result = get_next_binary_palindrome(d);
fprintf('%d -> %d (%s)\n',d,result,dec2bin(result));

1000000000000000 -> 1000000047151815 (11100011010111111010100111100101011111101011000111)

[Ken Bannister]

AWESOME!!!

Answer 2

[Walter Roberson]

There are two cases.

In the first case, the first half of the number is greater or equal to the reflected second half of the number. In such a case, the least palindrome is the first half of the number followed by its reflection.

For example

10110 00110

becomes

10110 01101

In the second case, the first half of the number is less than the reflected second half of the number. In such a case, the least palindorme is formed by adding 1 to the first half of the number (extending it if need be) and then reflecting that.

For example

10110 01110

becomes

10111 11101

These algorithms need to be touched up a bit if the length of the original number is odd

[Torsten]

What about the case given by the OP ? Original number 1 1 1 1 and least largest palindrome 1 0 0 0 1 ?

[Walter Roberson]

1111

divide into

11 11

the two halves are equal so this is already a palindrome.

Add one to the first half producing

100

reflect producing

100 001

but as indicated there needs to be some touch-up to the rules for the case of odd lengths

[Sam Chak]

I believe that @Walter Roberson's proposed solution works in the following manner:

format longG
d   = 15;           % decimal system
b   = dec2bin(d)    % binary system

b = '1111'

% length of bits
n   = length(b);    % may need to create rules for odd-numbered bits

% left-half of binary number
b1  = b(1:n/2)

b1 = '11'

% plus 1 (new left-half)
bL  = dec2bin(bin2dec(b1) + 1)

bL = '100'

% flip bits (right-half)
bL1 = bL(1:2)       % need to create If-Else rules here

bL1 = '10'

bR  = fliplr(bL1)

bR = '01'

% Concatenate bL and bR to form Palindromic bits 
pb  = [bL, bR]

pb = '10001'

% Convert back binary to decimal number
d3  = bin2dec(pb)

d3 = 
    17

[DGM]

That's way simpler than I thought it would be based on the formulae given.

Answer 3

[Image Analyst]

Can't you just do

b = dec2bin(d+1)

If not, then I'm not sure what you want. I'm not sure how 17 is the smallest natural number after 15.

[Torsten]

I think the OP means the least binary number greater than d that gives the same binary representation if read from left to right or if read from right to left. 16 wouldn't be such a number because

dec2bin(16)

ans = '10000'

[Image Analyst]

OK thanks for clarifying for me. This sounds quirky enough to be a homework problem, at least I can't see any real world use case for it. @Ken Bannister is it your homework? And it seems like one way would be just a brute force for loop to check.