login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of terms in greedy partition of n into binary palindromes.
2

%I #27 May 14 2018 07:45:40

%S 0,1,2,1,2,1,2,1,2,1,2,3,2,3,2,1,2,1,2,3,2,1,2,3,2,3,2,1,2,3,2,1,2,1,

%T 2,3,2,3,2,3,2,3,2,3,4,1,2,3,2,3,2,1,2,3,2,3,2,3,2,3,2,3,4,1,2,1,2,3,

%U 2,3,2,3,2,1,2,3,2,3,2,3,2,3,2,3,4,1,2,3,2,3,2,3,2,1,2,3,2,3,2,1

%N Number of terms in greedy partition of n into binary palindromes.

%C The definition and early trajectory are strikingly reminiscent of A259656. The first difference between the two sequences is at n = 38, where A259656 has 4 and this sequence has 2.

%C Start with n, and repeatedly subtract the largest possible binary palindrome that leaves a nonnegative residue. This sequence gives the number of such steps needed to reach 0.

%C This sequence is unbounded, since the gaps between binary palindromes are arbitrarily large, but it grows very slowly.

%C If we search for the smallest partition into binary palindromes, not necessarily greedy, we get another sequence dominated by this one. The first difference is at n = 44. It is believed that this smaller sequence is bounded, but I have not been able to find a claim of the maximum. See Cilleruelo and Luca 2016.

%C The position where n = 0.. occurs for the first time: 0, 1, 2, 11, 44, 557, 131630, ... - _Antti Karttunen_ and _Altug Alkan_, May 13 2018

%H Antti Karttunen, <a href="/A303536/b303536.txt">Table of n, a(n) for n = 0..65537</a>

%H Javier Cilleruelo and Florian Luca, <a href="https://www.uam.es/personal_pdi/ciencias/cillerue/Papers/three%20palindromes%20are%20enough%20-%202016-.pdf">Every Positive Integer is a Sum of Three Palindromes</a>.

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F a(0) = 0; for n > 0, a(n) = 1 + a(A303534(n)). [We are iterating the map n -> A303534(n) until zero is reached.] - _Antti Karttunen_, May 13 2018, after an earlier comment.

%e For n = 44:

%e The largest palindrome not exceeding 44 is 33 (100001). 44 - 33 = 11.

%e The largest palindrome not exceeding 11 is 9 (1001). 11 - 9 = 2.

%e The largest palindrome not exceeding 2 is 1. 2 - 1 = 1.

%e The largest palindrome not exceeding 1 is 1. 1 - 1 = 0.

%e The iteration took 4 steps to reach 0, so a(44) = 4.

%e For n = 131630; A303534(131630) = 557 and A303534(557) = 44. Since a(44) = 4 (as above), a(557) = 5 and a(131630) = 6. - _Altug Alkan_, Apr 26 2018

%o (PARI)

%o isA006995(n) = Vecrev(n=binary(n))==n;

%o A303534(n) = {my(k=0); while(!isA006995(n-k), k++); k; } \\ From A303534

%o A303536(n) = if(!n,n,1+A303536(A303534(n))); \\ _Antti Karttunen_, May 13 2018

%Y Cf. A006995 (binary palindromes), A206913, A259656, A303534.

%K nonn,base,easy

%O 0,3

%A _Allan C. Wechsler_, Apr 25 2018

%E More terms from _Altug Alkan_, Apr 25 2018