login
Numbers whose binary expansion is not palindromic.
14

%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