A154809 - OEIS

A154809

Numbers whose binary expansion is not palindromic.

2, 4, 6, 8, 10, 11, 12, 13, 14, 16, 18, 19, 20, 22, 23, 24, 25, 26, 28, 29, 30, 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 47, 48, 49, 50, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 64, 66, 67, 68, 69, 70, 71, 72, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 86, 87, 88

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

Complement of A006995.

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

A145799(a(n)) < a(n). - Reinhard Zumkeller, Sep 24 2015

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

FORMULA

A030101(n) != n. - David W. Wilson, Jun 09 2009

A178225(a(n)) = 0. - Reinhard Zumkeller, Oct 21 2011

From Hieronymus Fischer, Feb 19 2012 and Mar 18 2012: (Start)

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)).

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).

Example 1: d=1000, A206913(d)=975, A206915(975)=62, hence n=1001-62=939.

Example 2: d=10^6, A206913(d)=999471, A206915(999471)=2000, hence n=1000001-2000=998001.

Recursion formulas:

a(n+1)=a(n)+1+A178225(a(n)+1)

Also:

Case 1: a(n+1)=a(n)+2, if A206914(a(n))=a(n)+1;

Case 2: a(n+1)=a(n)+1, else.

Also:

Case 1: a(n+1)=a(n)+1, if A206914(a(n))>a(n)+1;

Case 2: a(n+1)=a(n)+2, else.

Iterative calculation formula:

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)).

Example 3: n=1000, f(0)=1001, f(1)=1061, f(2)=1064=f(3), hence a(1000)=1064.

Example 4: n=10^6, f(0)=10^6+1, f(1)=1001999, f(2)=1002001=f(3), hence a(10^6)=1002001.

Formula identity:

a(n) = n-1 + A206915(A206913(a(n))).

(End)

EXAMPLE

a(1)=2, since 2 = 10_2 is not binary palindromic.

MAPLE

ispali:= proc(n) local L;

L:= convert(n, base, 2);

ListTools:-Reverse(L)=L

end proc:

remove(ispali, [$1..1000]); # Robert Israel, Jul 05 2015

MATHEMATICA

palQ[n_Integer, base_Integer]:=Module[{idn=IntegerDigits[n, base]}, idn==Reverse[idn]]; Select[Range[1000], ! palQ[#, 2] &] (* Vincenzo Librandi, Jul 05 2015 *)

PROG

(Haskell)

a154809 n = a154809_list !! (n-1)

a154809_list = filter ((== 0) . a178225) [0..]

(Magma) [n: n in [0..600] | not (Intseq(n, 2) eq Reverse(Intseq(n, 2)))]; // Vincenzo Librandi, Jul 05 2015

(PARI) isok(n) = binary(n) != Vecrev(binary(n)); \\ Michel Marcus, Jul 05 2015

(Python)

def A154809(n):

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

m, k = n, f(n)

while m != k:

m, k = k, f(k)