A059906 Index of second half of decomposition of integers into pairs based on A000695.

0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3, 4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7, 4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3, 4, 4, 5, 5, 4, 4, 5, 5, 6

Offset: 0

Author

Marc LeBrun, Feb 07 2001

Keywords

• easy
• look
• nonn

Comments

One coordinate of a recursive non-self-intersecting walk on the square lattice Z^2.

Examples

			A000695(A059905(14)) + 2*A000695(a(14)) = A000695(2) + 2*A000695(3) = 4 + 2*5 = 14.
If n=27, then b_0=1, b_1=1, b_2=0, b_3=1, b_4=1. Therefore a(27) = b_1 + b_3*2 = 3. - _Vladimir Shevelev_, Nov 13 2008
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..8192
• G. M. Morton, A Computer Oriented Geodetic Data Base; and a New Technique in File Sequencing, IBM, 1966, with a(n) being section 5.1 step (b).
• Index entries for sequences related to coordinates of 2D curves

Crossrefs

Cf. A000695, A057300, A059905.

Programs

Mathematica

a[n_] := Module[{P}, (P = Partition[IntegerDigits[n, 2]//Reverse, 2][[All, 2]]).(2^(Range[Length[P]]-1))]; Array[a, 105, 0] (* Jean-François Alcover, Apr 24 2019 *)

PARI

A059906(n) = { my(t=1,s=0); while(n>0, s += ((n%4)>=2)*t; n \= 4; t *= 2); (s); }; \\ Antti Karttunen, Apr 14 2018

Python

def a(n):
    x=[int(t) for t in list(bin(n)[2:])[::-1]]
    return sum(x[2*i + 1]*2**i for i in range(int(len(x)//2)))
print([a(n) for n in range(105)]) # Indranil Ghosh, Jun 25 2017

Python

def A059906(n): return 0 if n < 2 else int(bin(n)[-2:1:-2][::-1],2) # Chai Wah Wu, Jun 30 2022

Formula

n = A000695(A059905(n)) + 2*A000695(a(n))

To get a(n), write n as Sum b_j*2^j, then a(n) = Sum b_(2j+1)*2^j. - Vladimir Shevelev, Nov 13 2008

a(n) = Sum_{k>=0} A030308(n,k)*b(k) with b(0)=0 and b(k)=A077957(k-1) for k>0. - Philippe Deléham, Oct 18 2011

Conjecture: a(n) = n - (1/2)*Sum_{k=1..n} (sqrt(2)^A007814(k) + (-sqrt(2))^A007814(k)) = -Sum_{k=1..n} (-1)^k * 2^floor(k/2) * floor(n/2^k). - Velin Yanev, Dec 01 2016