cp's OEIS Frontend

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

%I A303536 #27 May 14 2018 07:45:40
%S A303536 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 A303536 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 A303536 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 A303536 Number of terms in greedy partition of n into binary palindromes.
%C A303536 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 A303536 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 A303536 This sequence is unbounded, since the gaps between binary palindromes are arbitrarily large, but it grows very slowly.
%C A303536 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 A303536 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 A303536 Antti Karttunen, <a href="/A303536/b303536.txt">Table of n, a(n) for n = 0..65537</a>
%H A303536 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 A303536 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A303536 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 A303536 For n = 44:
%e A303536 The largest palindrome not exceeding 44 is 33 (100001). 44 - 33 = 11.
%e A303536 The largest palindrome not exceeding 11 is 9 (1001). 11 - 9 = 2.
%e A303536 The largest palindrome not exceeding 2 is 1. 2 - 1 = 1.
%e A303536 The largest palindrome not exceeding 1 is 1. 1 - 1 = 0.
%e A303536 The iteration took 4 steps to reach 0, so a(44) = 4.
%e A303536 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 A303536 (PARI)
%o A303536 isA006995(n) = Vecrev(n=binary(n))==n;
%o A303536 A303534(n) = {my(k=0); while(!isA006995(n-k), k++); k; } \\ From A303534
%o A303536 A303536(n) = if(!n,n,1+A303536(A303534(n))); \\ _Antti Karttunen_, May 13 2018
%Y A303536 Cf. A006995 (binary palindromes), A206913, A259656, A303534.
%K A303536 nonn,base,easy
%O A303536 0,3
%A A303536 _Allan C. Wechsler_, Apr 25 2018
%E A303536 More terms from _Altug Alkan_, Apr 25 2018