login
Index of first half of decomposition of integers into pairs based on A000695.
29

%I #68 Jul 01 2022 09:41:07

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

%T 0,1,2,3,2,3,0,1,0,1,2,3,2,3,4,5,4,5,6,7,6,7,4,5,4,5,6,7,6,7,8,9,8,9,

%U 10,11,10,11,8,9,8,9,10,11,10,11,12,13,12,13,14,15,14,15,12,13,12,13,14

%N Index of first half of decomposition of integers into pairs based on A000695.

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

%H Peter Kagey, <a href="/A059905/b059905.txt">Table of n, a(n) for n = 0..8192</a>

%H G. M. Morton, <a href="https://dominoweb.draco.res.ibm.com/0dabf9473b9c86d48525779800566a39.html">A Computer Oriented Geodetic Data Base; and a New Technique in File Sequencing</a>, IBM, 1966, with a(n) being section 5.1 step (c).

%H <a href="/index/Con#coordinates_2D_curves">Index entries for sequences related to coordinates of 2D curves</a>

%F n = A000695(a(n)) + 2*A000695(A059906(n)).

%F To get a(n), write n as Sum b_j*2^j, then a(n) = Sum b_(2j)*2^j. - _Vladimir Shevelev_, Nov 13 2008

%F a(n) = Sum_{k>=0} A030308(n,k)*A077957(k). - _Philippe Deléham_, Oct 18 2011

%F G.f.: (1-x)^(-1) * Sum_{j>=0} 2^j*x^(2^j)/(1+x^(2^j)). - _Robert Israel_, Aug 12 2015

%F a(n) = A059906(2*n). - _Velin Yanev_, Dec 01 2016

%e A000695(a(14)) + 2*A000695(A059906(14)) = A000695(2) + 2*A000695(3) = 4 + 2*5 = 14.

%e If n=27, then b_0=1, b_1=1, b_2=0, b_3=1, b_4=1. Therefore a(27) = b_0 + b_2*2 + b_4*2^2 = 5. - _Vladimir Shevelev_, Nov 13 2008

%p f:= proc(n) local L; L:= convert(n,base,2); add(L[2*i+1]*2^i,i=0..floor((nops(L)-1)/2)) end;

%p map(f, [$0..256]); # _Robert Israel_, Aug 12 2015

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

%o (Ruby)

%o def a(n)

%o (0..n.bit_length/2).to_a.map { |i| (n >> 2 * i & 1) << i}.reduce(:+)

%o end # _Peter Kagey_, Aug 12 2015

%o (Python)

%o def a(n): return sum([(n>>2*i&1)<<i for i in range(len(bin(n)[2:])//2 + 1)])

%o print([a(n) for n in range(101)]) # _Indranil Ghosh_, Jun 25 2017, after Ruby code by _Peter Kagey_

%o (Python)

%o def A059905(n): return int(bin(n)[:1:-2][::-1],2) # _Chai Wah Wu_, Jun 30 2022

%o (PARI) A059905(n) = { my(t=1,s=0); while(n>0, s += (n%2)*t; n \= 4; t *= 2); (s); }; \\ _Antti Karttunen_, Apr 14 2018

%Y Cf. A000695, A030308, A059906, A057300, A077957.

%K easy,nonn,look

%O 0,5

%A _Marc LeBrun_, Feb 07 2001