%I #49 Jul 24 2024 14:22:06
%S 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 36,37,38,39,40,41,42,43,44,46,47,48,49,50,52,53,54,55,56,57,58,59,60,
%U 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 Numbers whose binary expansion is not palindromic.
%C Complement of A006995.
%C 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 A145799(a(n)) < a(n). - _Reinhard Zumkeller_, Sep 24 2015
%H Reinhard Zumkeller, <a href="/A154809/b154809.txt">Table of n, a(n) for n = 1..10000</a>
%F A030101(n) != n. - _David W. Wilson_, Jun 09 2009
%F A178225(a(n)) = 0. - _Reinhard Zumkeller_, Oct 21 2011
%F From _Hieronymus Fischer_, Feb 19 2012 and Mar 18 2012: (Start)
%F 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 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 Example 1: d=1000, A206913(d)=975, A206915(975)=62, hence n=1001-62=939.
%F Example 2: d=10^6, A206913(d)=999471, A206915(999471)=2000, hence n=1000001-2000=998001.
%F Recursion formulas:
%F a(n+1)=a(n)+1+A178225(a(n)+1)
%F Also:
%F Case 1: a(n+1)=a(n)+2, if A206914(a(n))=a(n)+1;
%F Case 2: a(n+1)=a(n)+1, else.
%F Also:
%F Case 1: a(n+1)=a(n)+1, if A206914(a(n))>a(n)+1;
%F Case 2: a(n+1)=a(n)+2, else.
%F Iterative calculation formula:
%F 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 Example 3: n=1000, f(0)=1001, f(1)=1061, f(2)=1064=f(3), hence a(1000)=1064.
%F Example 4: n=10^6, f(0)=10^6+1, f(1)=1001999, f(2)=1002001=f(3), hence a(10^6)=1002001.
%F Formula identity:
%F a(n) = n-1 + A206915(A206913(a(n))).
%F (End)
%e a(1)=2, since 2 = 10_2 is not binary palindromic.
%p ispali:= proc(n) local L;
%p L:= convert(n,base,2);
%p ListTools:-Reverse(L)=L
%p end proc:
%p remove(ispali, [$1..1000]); # _Robert Israel_, Jul 05 2015
%t palQ[n_Integer, base_Integer]:=Module[{idn=IntegerDigits[n, base]}, idn==Reverse[idn]]; Select[Range[1000], ! palQ[#, 2] &] (* _Vincenzo Librandi_, Jul 05 2015 *)
%o (Haskell)
%o a154809 n = a154809_list !! (n-1)
%o a154809_list = filter ((== 0) . a178225) [0..]
%o (Magma) [n: n in [0..600] | not (Intseq(n, 2) eq Reverse(Intseq(n, 2)))]; // _Vincenzo Librandi_, Jul 05 2015
%o (PARI) isok(n) = binary(n) != Vecrev(binary(n)); \\ _Michel Marcus_, Jul 05 2015
%o (Python)
%o def A154809(n):
%o 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 m, k = n, f(n)
%o while m != k:
%o m, k = k, f(k)
%o return m # _Chai Wah Wu_, Jul 24 2024
%Y Cf. A006995, A154810, A164861, A206913, A206915.
%Y Cf. A145799.
%K easy,nonn,base
%O 1,1
%A _Omar E. Pol_, Jan 24 2009
%E Extended by _Ray Chandler_, Mar 14 2010