A000695 -id:A000695 - cp's OEIS frontend

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

Marc LeBrun, Feb 07 2001

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

			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

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

Cf. A000695, A057300, A059905.

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

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

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

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

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

A302846 Interleave the Gray-coded X and Y-coordinates of 2-dimensional Hilbert's curve in alternate bit-positions: a(n) = A000695(A003188(A059253(n))) + 2*A000695(A003188(A059252(n))).

Original entry on oeis.org

0, 1, 3, 2, 10, 8, 9, 11, 15, 13, 12, 14, 6, 7, 5, 4, 20, 22, 23, 21, 17, 16, 18, 19, 27, 26, 24, 25, 29, 31, 30, 28, 60, 62, 63, 61, 57, 56, 58, 59, 51, 50, 48, 49, 53, 55, 54, 52, 36, 37, 39, 38, 46, 44, 45, 47, 43, 41, 40, 42, 34, 35, 33, 32, 160, 162, 163, 161, 165, 164, 166, 167, 175, 174, 172, 173, 169, 171, 170, 168, 136

Offset: 0

Antti Karttunen, Apr 14 2018

Like in binary Gray code A003188, also in this permutation the binary expansions of a(n) and a(n+1) differ always by just a single bit-position, that is, A000120(A003987(a(n),a(n+1))) = 1 for all n >= 0. Here A003987 computes bitwise-XOR of its two arguments.

When composed with A052330 this gives A302781.

Cf. A302845 (inverse permutation).
Cf. A000695, A302844, A057300, A059252, A059253, A064706, A163356, A302781.
Cf. also A003188, A163252, A300838 for other permutations satisfying the same condition.

A064706(n) = bitxor(n, n>>2);
A057300(n) = { my(t=1,s=0); while(n>0, if(1==(n%4),n++,if(2==(n%4),n--)); s += (n%4)*t; n >>= 2; t <<= 2); (s); };
A163356(n) = if(!n,n,my(i = (#binary(n)-1)\2, f = 4^i, d = (n\f)%4, r = (n%f)); (((((2+(i%2))^d)%5)-1)*f) + if(3==d,f-1-A163356(r),A057300(A163356(r))));
A302846(n) = A064706(A163356(n));

a(n) = A000695(A003188(A059253(n))) + 2*A000695(A003188(A059252(n))).

a(n) = A064706(A163356(n)) = A003188(A302844(n)).

A126684 Union of A000695 and 2*A000695.

Original entry on oeis.org

0, 1, 2, 4, 5, 8, 10, 16, 17, 20, 21, 32, 34, 40, 42, 64, 65, 68, 69, 80, 81, 84, 85, 128, 130, 136, 138, 160, 162, 168, 170, 256, 257, 260, 261, 272, 273, 276, 277, 320, 321, 324, 325, 336, 337, 340, 341, 512, 514, 520, 522, 544, 546, 552, 554, 640, 642, 648, 650

Offset: 1

Jonathan Deane, Feb 15 2007, May 04 2007

Essentially the same as A032937: 0 followed by terms of A032937. - R. J. Mathar, Jun 15 2008
Previous name was: If A = {a_1, a_2, a_3...} is the Moser-de Bruijn sequence A000695 (consisting of sums of distinct powers of 4) and A' = {2a_1, 2a_2, 2a_3...} then this sequence, let's call it B, is the union of A and A'. Its significance, alluded to in the entry for the Moser-de Bruijn sequence, is that its sumset, B+B, = {b_i + b_j : i, j natural numbers} consists of the nonnegative integers; and it is the fastest-growing sequence with this property. It can also be described as a "basis of order two for the nonnegative integers".
The sequence is the fastest growing with this property in the sense that a(n) ~ n^2, and any sequence with this property is O(n^2). - Franklin T. Adams-Watters, Jul 27 2015
Or, base 2 representation Sum{d(i)*2^(m-i): i=0,1,...,m} has even d(i) for all odd i.
Union of A000695 and 2*A000695. - Ralf Stephan, May 05 2004
Union of A000695 and A062880. - Franklin T. Adams-Watters, Aug 30 2014
Integers, the binary representation of which contains no pair of 1 bits whose difference in bit index is odd. - Frederik P.J. Vandecasteele, May 29 2025

			All nonnegative integers can be represented in the form b_i + b_j; e.g. 6 = 5+1, 7 = 5+2, 8 = 0+8, 9 = 4+5

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.

Cf. A000695, A062880, A033053, A032937.

a126684 n = a126684_list !! (n-1)
a126684_list = tail $ m a000695_list $ map (* 2) a000695_list where
   m xs'@(x:xs) ys'@(y:ys) | x < y     = x : m xs ys'
                           | otherwise = y : m xs' ys
-- Reinhard Zumkeller, Dec 03 2011

nmax = 100;
b[n_] := FromDigits[IntegerDigits[n, 2], 4];
Union[A000695 = b /@ Range[0, nmax], 2 A000695][[1 ;; nmax+1]] (* Jean-François Alcover, Oct 28 2019 *)

for(n=0,350,b=binary(n); l=length(b); if(sum(i=1,floor(l/2), component(b,2*i))==0,print1(n,",")))

from gmpy2 import digits
def A126684(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def g(x):
        s = digits(x,4)
        for i in range(l:=len(s)):
            if s[i]>'1':
                break
        else:
            return int(s,2)
        return int(s[:i]+'1'*(l-i),2)
    def f(x): return n-1+x-g(x)-g(x>>1)
    return bisection(f,n-1,n-1) # Chai Wah Wu, Oct 29 2024

G.f.: sum(i>=1, T(i, x) + U(i, x) ), where
T := (k,x) -> x^(2^k-1)*V(k,x);
U := (k,x) -> 2*x^(3*2^(k-1)-1)*V(k,x); and
V := (k,x) -> (1-x^(2^(k-1)))*(4^(k-1) + sum(4^j*x^(2^j)/(1+x^(2^j)), j = 0..k-2))/(1-x);
Generating function. Define V(k) := [4^(k-1) + Sum ( j=0 to k-2, 4^j * x^(2^j)/(1+x^(2^j)) )] * (1-x^(2^(k-1)))/(1-x) and T(k) := (x^(2^k-1) * V(k), U(k) := x^(3*2^(k-1)-1) * V(k) then G.f. is Sum ( i >= 1, T(i) + U(i) ). Functional equation: if the sequence is a(n), n = 1, 2, 3, ... and h(x) := Sum ( n >= 1, x^a(n) ) then h(x) satisfies the following functional equation: (1 + x^2)*h(x^4) - (1 - x)*h(x^2) - x*h(x) + x^2 = 0.

New name (using comment from Ralf Stephan) from Joerg Arndt, Aug 31 2014

A152021 Numbers a(n) are obtained by the direct application of sieve of Eratosthenes for A000695: retaining A000695(2)=4, we delete all multiples of 4, which are more than 4; retaining A000695(3)=5, we delete all multiples of 5, which are more than 5, etc.

Original entry on oeis.org

4, 5, 17, 21, 69, 81, 257, 261, 277, 321, 337, 341, 1041, 1089, 1093, 1109, 1297, 1301, 1349, 1361, 4101, 4113, 4117, 4161, 4177, 4181, 4353, 4357, 4373, 4417, 4421, 5121, 5137, 5141, 5189, 5201, 5377, 5381, 5393, 5441, 5461, 16389, 16449, 16453, 16469, 16641

Offset: 1

Vladimir Shevelev, Nov 20 2008

nonn

If p is prime, then A000695(p) is in the sequence; but, e. g., A000695(25), A000695(55) are also in the sequence.

Cf. A000695.

Contribution from R. J. Mathar, Oct 29 2010: (Start)
A000695 := proc(n) local dgsa ; if n= 0 then 0; else for a from procname(n-1)+1 do dgsa := convert(convert(a,base,4),set) ; if dgsa minus {0,1} = {} then return a; end if; end do: end if; end proc:
A152021 := proc(nmax) a := [seq(A000695(i),i=2..nmax)] ; ptr := 1; while ptr < nops(a) do for j from nops(a) to ptr+1 by -1 do if op(j,a) mod op(ptr,a) = 0 then a := subsop(j=NULL,a) ; end if; end do: ptr := ptr+1 ; end do: a ; end proc: A152021(120) ; (End)

f[n_] := FromDigits[IntegerDigits[n, 2], 4]; s = Array[f, 150, 2]; div[a_, b_] := Divisible[a, b] && a > b; n = 1; While[Length[s] > n, s = Select[s, !div[#, s[[n]]] &]; n++]; s (* Amiram Eldar, Aug 31 2019 *)

More terms from R. J. Mathar, Oct 29 2010

More terms from Amiram Eldar, Aug 31 2019

A152022 Numbers > 1 in A000695 which are not in A152021.

Original entry on oeis.org

16, 20, 64, 65, 68, 80, 84, 85, 256, 260, 272, 273, 276, 320, 324, 325, 336, 340, 1024, 1025, 1028, 1029, 1040, 1044, 1045, 1088, 1092, 1104, 1105, 1108, 1280, 1281, 1284, 1285, 1296, 1300, 1344, 1345, 1348, 1360, 1364, 1365, 4096, 4097, 4100

Offset: 1

Vladimir Shevelev, Nov 20 2008

nonn

Cf. A000695, A152021.

f[n_] := FromDigits[IntegerDigits[n, 2], 4];  s = Array[f, 100, 2]; div[a_, b_] := Divisible[a, b] && a > b; n = 1; s0 = s; While[Length[s] > n, s = Select[s, ! div[#, s[[n]]] &]; n++]; Complement[s0, s] (* Amiram Eldar, Aug 31 2019 *)

A152078 Numbers a(n) for which A000695(a(n)) = A077718(n).

Original entry on oeis.org

3, 5, 17, 23, 29, 43, 47, 53, 55, 61, 77, 83, 87, 91, 107, 115, 117, 121, 139, 149, 151, 171, 173, 179, 181, 185, 191, 203, 213, 229, 233, 239, 253, 257, 263, 269, 277, 299, 307, 327, 329, 353, 369, 379, 383, 389, 405, 409, 415, 425, 439, 443, 449, 471, 475, 477

Offset: 1

Vladimir Shevelev, Nov 23 2008

nonn

			If n=1, then a(1)=3, A000695(3)=5=A077718(1).

Cf. A000695, A077718, A152021, A152022, A152023.

f[n_] := FromDigits[IntegerDigits[n, 2], 4]; Select[Range[500], PrimeQ[f[#]] &] (* Amiram Eldar, Aug 31 2019 *)

More terms from Amiram Eldar, Aug 31 2019

A152754 "Upper positive integers": n is in the sequence iff in the representation n=A000695(k)+2*A000695(l) satisfies inequality A000695(k) < A000695(l).

Original entry on oeis.org

2, 8, 9, 10, 11, 14, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 50, 56, 57, 58, 59, 62, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160

Offset: 1

Vladimir Shevelev, Dec 12 2008

nonn

In the mapping: every integer m corresponds to a unique pair (k,l) with m=A000695(k)+2*A000695(l) (k=A059905(m), l=A059906(m)), the numbers a(n) are mapped into the lattice points lying upper the diagonal l=k. If the binary expansion of N is Sum b_j*2^j, then N is in the sequence iff Sum b_(2j)*2^jA139370. This explains, somewhat, why many terms of the sequence are in A139370 as well.

Vincenzo Librandi, Table of n, a(n) for n = 1..8128

Cf. A000695, A139370.

fh[n_,h_] := If[h==1, Mod[n,2], If[Mod[n,4]>=2,1,0]]; half[n_, h_ ] := Module[{t=1, s=0, m=n}, While[m>0, s += fh[m,h]*t; m=Quotient[m,4]; t *= 2]; s]; mb[n_] := FromDigits[Riffle[IntegerDigits[n, 2], 0], 2]; aQ[n_] := mb[half[n,1]] < mb[half[n, 2]]; Select[Range[160], aQ] (* Amiram Eldar, Dec 16 2018 from the PARI code *)

a000695(n) = fromdigits(binary(n), 4);
half1(n) = { my(t=1, s=0); while(n>0, s += (n%2)*t; n \= 4; t *= 2); (s); }; \\ A059905
half2(n) = { my(t=1, s=0); while(n>0, s += ((n%4)>=2)*t; n \= 4; t *= 2); (s); }; \\ A059906
isok(n) = a000695(half1(n)) < a000695(half2(n)); \\ Michel Marcus, Dec 15 2018

Missing 9 and more terms from Michel Marcus, Dec 15 2018

A278238 a(n) = A278233(A000695(n)) = A278233(n)^2.

Original entry on oeis.org

1, 4, 4, 16, 16, 36, 4, 64, 36, 144, 4, 144, 4, 36, 64, 256, 256, 900, 4, 1296, 16, 36, 36, 576, 4, 36, 144, 144, 36, 576, 4, 1024, 36, 2304, 36, 3600, 4, 36, 144, 5184, 4, 144, 36, 144, 576, 900, 4, 2304, 36, 36, 1024, 144, 36, 3600, 4, 576, 144, 900, 4, 5184, 4, 36, 144

Offset: 1

Antti Karttunen, Nov 17 2016

nonn

Cf. A048720, A000695, A278233, A278239, A278254.

(define (A278238 n) (A278233 (A000695 n)))

a(n) = A278233(A000695(n)).

a(n) = A278233(n)^2.

cp's OEIS Frontend

A152079 Primes p such that A000695(p) are also prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Ruby

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Python

Formula

A302846 Interleave the Gray-coded X and Y-coordinates of 2-dimensional Hilbert's curve in alternate bit-positions: a(n) = A000695(A003188(A059253(n))) + 2*A000695(A003188(A059252(n))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A126684 Union of A000695 and 2*A000695.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Formula

Extensions

A152021 Numbers a(n) are obtained by the direct application of sieve of Eratosthenes for A000695: retaining A000695(2)=4, we delete all multiples of 4, which are more than 4; retaining A000695(3)=5, we delete all multiples of 5, which are more than 5, etc.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Mathematica

Extensions

A152022 Numbers > 1 in A000695 which are not in A152021.

Views

Author

Keywords