cp's OEIS Frontend

A154809 Numbers whose binary expansion is not palindromic.

%I A154809 #49 Jul 24 2024 14:22:06
%S A154809 2,4,6,8,10,11,12,13,14,16,18,19,20,22,23,24,25,26,28,29,30,32,34,35,
%T A154809 36,37,38,39,40,41,42,43,44,46,47,48,49,50,52,53,54,55,56,57,58,59,60,
%U A154809 61,62,64,66,67,68,69,70,71,72,74,75,76,77,78,79,80,81,82,83,84,86,87,88
%N A154809 Numbers whose binary expansion is not palindromic.
%C A154809 Complement of A006995.
%C A154809 The (a(n)-n+1)-th binary palindrome equals the greatest binary palindrome <= a(n). The corresponding formula identity is: A006995(a(n)-n+1)=A206913(a(n)). - _Hieronymus Fischer_, Mar 18 2012
%C A154809 A145799(a(n)) < a(n). - _Reinhard Zumkeller_, Sep 24 2015
%H A154809 Reinhard Zumkeller, <a href="/A154809/b154809.txt">Table of n, a(n) for n = 1..10000</a>
%F A154809 A030101(n) != n. - _David W. Wilson_, Jun 09 2009
%F A154809 A178225(a(n)) = 0. - _Reinhard Zumkeller_, Oct 21 2011
%F A154809 From _Hieronymus Fischer_, Feb 19 2012 and Mar 18 2012: (Start)
%F A154809 Inversion formula: If d is any number from this sequence, then the index number n for which a(n)=d can be calculated by n=d+1-A206915(A206913(d)).
%F A154809 Explicitly: Let p=A206913(d), m=floor(log_2(p)) and p>2, then: a(n)=d+1+(((5-(-1)^m)/2) + sum(k=1...floor(m/2)|(floor(p/2^k) mod 2)/2^k))*2^floor(m/2).
%F A154809 Example 1: d=1000, A206913(d)=975, A206915(975)=62, hence n=1001-62=939.
%F A154809 Example 2: d=10^6, A206913(d)=999471, A206915(999471)=2000, hence n=1000001-2000=998001.
%F A154809 Recursion formulas:
%F A154809 a(n+1)=a(n)+1+A178225(a(n)+1)
%F A154809 Also:
%F A154809   Case 1: a(n+1)=a(n)+2, if A206914(a(n))=a(n)+1;
%F A154809   Case 2: a(n+1)=a(n)+1, else.
%F A154809 Also:
%F A154809   Case 1: a(n+1)=a(n)+1, if A206914(a(n))>a(n)+1;
%F A154809   Case 2: a(n+1)=a(n)+2, else.
%F A154809 Iterative calculation formula:
%F A154809 Let f(0):=n+1, f(j):=n-1+A206915(A206913(f(j-1)) for j>0; then a(n)=f(j), if f(j)=f(j-1). The number of necessary steps is typically <4 and is limited by O(log_2(n)).
%F A154809 Example 3: n=1000, f(0)=1001, f(1)=1061, f(2)=1064=f(3), hence a(1000)=1064.
%F A154809 Example 4: n=10^6, f(0)=10^6+1, f(1)=1001999, f(2)=1002001=f(3), hence a(10^6)=1002001.
%F A154809 Formula identity:
%F A154809 a(n) = n-1 + A206915(A206913(a(n))).
%F A154809 (End)
%e A154809 a(1)=2, since 2 = 10_2 is not binary palindromic.
%p A154809 ispali:= proc(n) local L;
%p A154809 L:= convert(n,base,2);
%p A154809 ListTools:-Reverse(L)=L
%p A154809 end proc:
%p A154809 remove(ispali, [$1..1000]); # _Robert Israel_, Jul 05 2015
%t A154809 palQ[n_Integer, base_Integer]:=Module[{idn=IntegerDigits[n, base]}, idn==Reverse[idn]]; Select[Range[1000], ! palQ[#, 2] &] (* _Vincenzo Librandi_, Jul 05 2015 *)
%o A154809 (Haskell)
%o A154809 a154809 n = a154809_list !! (n-1)
%o A154809 a154809_list = filter ((== 0) . a178225) [0..]
%o A154809 (Magma) [n: n in [0..600] | not (Intseq(n, 2) eq Reverse(Intseq(n, 2)))]; // _Vincenzo Librandi_, Jul 05 2015
%o A154809 (PARI) isok(n) = binary(n) != Vecrev(binary(n)); \\ _Michel Marcus_, Jul 05 2015
%o A154809 (Python)
%o A154809 def A154809(n):
%o A154809     def f(x): return n+(x>>(l:=x.bit_length())-(k:=l+1>>1))-(int(bin(x)[k+1:1:-1],2)>(x&(1<<k)-1))+(1<<k-1+(l&1^1))-1
%o A154809     m, k = n, f(n)
%o A154809     while m != k:
%o A154809         m, k = k, f(k)
%o A154809     return m # _Chai Wah Wu_, Jul 24 2024
%Y A154809 Cf. A006995, A154810, A164861, A206913, A206915.
%Y A154809 Cf. A145799.
%K A154809 easy,nonn,base
%O A154809 1,1
%A A154809 _Omar E. Pol_, Jan 24 2009
%E A154809 Extended by _Ray Chandler_, Mar 14 2010