cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Previous Showing 11-20 of 214 results. Next

A270200 a(0) = 0; for n >= 1, a(n) = A054429(A005187(1+A054429(n-1))).

Original entry on oeis.org

0, 1, 2, 4, 7, 8, 12, 13, 15, 16, 21, 22, 24, 25, 28, 29, 31, 32, 38, 39, 41, 42, 45, 46, 48, 49, 53, 54, 56, 57, 60, 61, 63, 64, 71, 72, 74, 75, 78, 79, 81, 82, 86, 87, 89, 90, 93, 94, 96, 97, 102, 103, 105, 106, 109, 110, 112, 113, 117, 118, 120, 121, 124, 125, 127, 128, 136, 137, 139, 140, 143, 144, 146, 147, 151
Offset: 0

Views

Author

Antti Karttunen, May 31 2016

Keywords

Comments

After the initial zero, numbers that occur in the range of A233272.

Links

Crossrefs

Complement: A270198.
Cf. A005187, A054429, A233272, A233273.
Cf. also A233271 (a subsequence).

Programs

  • Mathematica
    s = Range[2^(# + 1) - 1, 2^#, -1] & /@ Range[0, 12] // Flatten; {0, 1}~Join~Table[s[[2 # - DigitCount[2 #, 2, 1] &[1 + s[[n - 1]]]]], {n, 2, 74}] (* Michael De Vlieger, Jun 01 2016, after Harvey P. Dale at A005187 and A054429 *)

Formula

a(0) = 0; for n >= 1, a(n) = A054429(A005187(1+A054429(n-1))).
Other identities. For all >= 0:
A233273(n) = a(n+2).

A005940 The Doudna sequence: write n-1 in binary; power of prime(k) in a(n) is # of 1's that are followed by k-1 0's.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 9, 8, 7, 10, 15, 12, 25, 18, 27, 16, 11, 14, 21, 20, 35, 30, 45, 24, 49, 50, 75, 36, 125, 54, 81, 32, 13, 22, 33, 28, 55, 42, 63, 40, 77, 70, 105, 60, 175, 90, 135, 48, 121, 98, 147, 100, 245, 150, 225, 72, 343, 250, 375, 108, 625, 162, 243, 64, 17, 26, 39
Offset: 1

Views

Author

N. J. A. Sloane and J. H. Conway

Keywords

Comments

A permutation of the natural numbers. - Robert G. Wilson v, Feb 22 2005
Fixed points: A029747. - Reinhard Zumkeller, Aug 23 2006
The even bisection, when halved, gives the sequence back. - Antti Karttunen, Jun 28 2014
From Antti Karttunen, Dec 21 2014: (Start)
This irregular table can be represented as a binary tree. Each child to the left is obtained by applying A003961 to the parent, and each child to the right is obtained by doubling the parent:
1
|
...................2...................
3 4
5......../ \........6 9......../ \........8
/ \ / \ / \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \
7 10 15 12 25 18 27 16
11 14 21 20 35 30 45 24 49 50 75 36 125 54 81 32
etc.
Sequence A163511 is obtained by scanning the same tree level by level, from right to left. Also in binary trees A253563 and A253565 the terms on level of the tree are some permutation of the terms present on the level n of this tree. A252464(n) gives the distance of n from 1 in all these trees.
A252737(n) gives the sum and A252738(n) the product of terms on row n (where 1 is on row 0, 2 on row 1, 3 and 4 on row 2, etc.). A252745(n) gives the number of nodes on level n whose left child is larger than the right child, A252750 the difference between left and right child for each node from node 2 onward.
(End)
-A008836(a(1+n)) gives the corresponding numerator for A323505(n). - Antti Karttunen, Jan 19 2019
(a(2n+1)-1)/2 [= A244154(n)-1, for n >= 0] is a permutation of the natural numbers. - George Beck and Antti Karttunen, Dec 08 2019
From Peter Munn, Oct 04 2020: (Start)
Each term has the same even part (equivalently, the same 2-adic valuation) as its index.
Using the tree depicted in Antti Karttunen's 2014 comment:
Numbers are on the right branch (4 and descendants) if and only if divisible by the square of their largest prime factor (cf. A070003).
Numbers on the left branch, together with 2, are listed in A102750.
(End)
According to Kutz (1981), he learned of this sequence from American mathematician Byron Leon McAllister (1929-2017) who attributed the invention of the sequence to a graduate student by the name of Doudna (first name Paul?) in the mid-1950's at the University of Wisconsin. - Amiram Eldar, Jun 17 2021
From David James Sycamore, Sep 23 2022: (Start)
Alternative (recursive) definition: If n is a power of 2 then a(n)=n. Otherwise, if 2^j is the greatest power of 2 not exceeding n, and if k = n - 2^j, then a(n) is the least m*a(k) that has not occurred previously, where m is an odd prime.
Example: Use recursion with n = 77 = 2^6 + 13. a(13) = 25 and since 11 is the smallest odd prime m such that m*a(13) has not already occurred (see a(27), a(29),a(45)), then a(77) = 11*25 = 275. (End)
The odd bisection, when transformed by replacing all prime(k)^e in a(2*n - 1) with prime(k-1)^e, returns a(n), and thus gives the sequence back. - David James Sycamore, Sep 28 2022

Examples

			From _N. J. A. Sloane_, Aug 22 2022: (Start)
Let c_i = number of 1's in binary expansion of n-1 that have i 0's to their right, and let p(j) = j-th prime.  Then a(n) = Product_i p(i+1)^c_i.
If n=9, n-1 is 1000, c_3 = 1, a(9) = p(4)^1 = 7.
If n=10, n-1 = 1001, c_0 = 1, c_2 = 1, a(10) = p(1)*p(3) = 2*5 = 10.
If n=11, n-1 = 1010, c_1 = 1, c_2 = 1, a(11) = p(2)*p(3) = 15. (End)

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A103969. Inverse is A005941 (A156552).
Cf. A125106. [From Franklin T. Adams-Watters, Mar 06 2010]
Cf. A252737 (gives row sums), A252738 (row products), A332979 (largest on row).
Related permutations of positive integers: A163511 (via A054429), A243353 (via A006068), A244154, A253563 (via A122111), A253565, A332977, A334866 (via A225546).
A000120, A003602, A003961, A006519, A053645, A070939, A246278, A250246, A252753, A253552 are used in a formula defining this sequence.
Formulas for f(a(n)) are given for f = A000265, A003963, A007949, A055396, A056239.
Numbers that occur at notable sets of positions in the binary tree representation of the sequence: A000040, A000079, A002110, A070003, A070826, A102750.
Cf. also A000142, A001511, A002450, A112798, A252463, A252464, A252745, A252750, A324054, A324106, A323505, A323508.
Cf. A106737, A290077, A323915, A324052, A324054, A324055, A324056, A324057, A324058, A324114, A324335, A324340, A324348, A324349 for various number-theoretical sequences applied to (i.e., permuted by) this sequence.
k-adic valuation: A007814 (k=2), A337821 (k=3).
Positions of multiples of 3: A091067.
Primorial deflation: A337376 / A337377.
Sum of prime indices of a(n) is A161511, reverse version A359043.
A048793 lists binary indices, ranked by A019565.
A066099 lists standard comps, partial sums A358134 (ranked by A358170).
Cf. A001222, A029837, A059893, A241916, A242628, A253566, A359042.

Programs

  • Haskell
    a005940 n = f (n - 1) 1 1 where
   f 0 y _          = y
   f x y i | m == 0 = f x' y (i + 1)
           | m == 1 = f x' (y * a000040 i) i
           where (x',m) = divMod x 2
-- Reinhard Zumkeller, Oct 03 2012
(Scheme, with memoization-macro definec from Antti Karttunen's IntSeq-library)
(define (A005940 n) (A005940off0 (- n 1))) ;; The off=1 version, utilizing any one of three different offset-0 implementations:
(definec (A005940off0 n) (cond ((< n 2) (+ 1 n)) (else (* (A000040 (- (A070939 n) (- (A000120 n) 1))) (A005940off0 (A053645 n))))))
(definec (A005940off0 n) (cond ((<= n 2) (+ 1 n)) ((even? n) (A003961 (A005940off0 (/ n 2)))) (else (* 2 (A005940off0 (/ (- n 1) 2))))))
(define (A005940off0 n) (let loop ((n n) (i 1) (x 1)) (cond ((zero? n) x) ((even? n) (loop (/ n 2) (+ i 1) x)) (else (loop (/ (- n 1) 2) i (* x (A000040 i)))))))
;; Antti Karttunen, Jun 26 2014
  • Maple
    f := proc(n,i,x) option remember ; if n = 0 then x; elif type(n,'even') then procname(n/2,i+1,x) ; else procname((n-1)/2,i,x*ithprime(i)) ; end if; end proc:
A005940 := proc(n) f(n-1,1,1) ; end proc: # R. J. Mathar, Mar 06 2010
  • Mathematica
    f[n_] := Block[{p = Partition[ Split[ Join[ IntegerDigits[n - 1, 2], {2}]], 2]}, Times @@ Flatten[ Table[q = Take[p, -i]; Prime[ Count[ Flatten[q], 0] + 1]^q[[1, 1]], {i, Length[p]}] ]]; Table[ f[n], {n, 67}] (* Robert G. Wilson v, Feb 22 2005 *)
Table[Times@@Prime/@(Join@@Position[Reverse[IntegerDigits[n,2]],1]-Range[DigitCount[n,2,1]]+1),{n,0,100}] (* Gus Wiseman, Dec 28 2022 *)
  • PARI
    A005940(n) = { my(p=2, t=1); n--; until(!n\=2, n%2 && (t*=p) || p=nextprime(p+1)); t } \\ M. F. Hasler, Mar 07 2010; update Aug 29 2014
  • PARI
    a(n)=my(p=2, t=1); for(i=0,exponent(n), if(bittest(n,i), t*=p, p=nextprime(p+1))); t \\ Charles R Greathouse IV, Nov 11 2021
  • Python
    from sympy import prime
import math
def A(n): return n - 2**int(math.floor(math.log(n, 2)))
def b(n): return n + 1 if n<2 else prime(1 + (len(bin(n)[2:]) - bin(n)[2:].count("1"))) * b(A(n))
print([b(n - 1) for n in range(1, 101)]) # Indranil Ghosh, Apr 10 2017
  • Python
    from math import prod
from itertools import accumulate
from collections import Counter
from sympy import prime
def A005940(n): return prod(prime(len(a)+1)**b for a, b in Counter(accumulate(bin(n-1)[2:].split('1')[:0:-1])).items()) # Chai Wah Wu, Mar 10 2023

Formula

From Reinhard Zumkeller, Aug 23 2006, R. J. Mathar, Mar 06 2010: (Start)
a(n) = f(n-1, 1, 1)
where f(n, i, x) = x if n = 0,
= f(n/2, i+1, x) if n > 0 is even
= f((n-1)/2, i, x*prime(i)) otherwise. (End)
From Antti Karttunen, Jun 26 2014: (Start)
Define a starting-offset 0 version of this sequence as:
b(0)=1, b(1)=2, [base cases]
and then compute the rest either with recurrence:
b(n) = A000040(1+(A070939(n)-A000120(n))) * b(A053645(n)).
or
b(2n) = A003961(b(n)), b(2n+1) = 2 * b(n). [Compare this to the similar recurrence given for A163511.]
Then define a(n) = b(n-1), where a(n) gives this sequence A005940 with the starting offset 1.
Can be also defined as a composition of related permutations:
a(n+1) = A243353(A006068(n)).
a(n+1) = A163511(A054429(n)). [Compare the scatter plots of this sequence and A163511 to each other.]
This permutation also maps between the partitions as enumerated in the lists A125106 and A112798, providing identities between:
A161511(n) = A056239(a(n+1)). [The corresponding sums ...]
A243499(n) = A003963(a(n+1)). [... and the products of parts of those partitions.]
(End)
From Antti Karttunen, Dec 21 2014 - Jan 04 2015: (Start)
A002110(n) = a(1+A002450(n)). [Primorials occur at (4^n - 1)/3 in the offset-0 version of the sequence.]
a(n) = A250246(A252753(n-1)).
a(n) = A122111(A253563(n-1)).
For n >= 1, A055396(a(n+1)) = A001511(n).
For n >= 2, a(n) = A246278(1+A253552(n)).
(End)
From Peter Munn, Oct 04 2020: (Start)
A000265(a(n)) = a(A000265(n)) = A003961(a(A003602(n))).
A006519(a(n)) = a(A006519(n)) = A006519(n).
a(n) = A003961(a(A003602(n))) * A006519(n).
A007814(a(n)) = A007814(n).
A007949(a(n)) = A337821(n) = A007814(A003602(n)).
a(n) = A225546(A334866(n-1)).
(End)
a(2n) = 2*a(n), or generally a(2^k*n) = 2^k*a(n). - Amiram Eldar, Oct 03 2022
If n-1 = Sum_{i} 2^(q_i-1), then a(n) = Product_{i} prime(q_i-i+1). These are the Heinz numbers of the rows of A125106. If the offset is changed to 0, the inverse is A156552. - Gus Wiseman, Dec 28 2022

Extensions

More terms from Robert G. Wilson v, Feb 22 2005
Sign in a formula switched and Maple program added by R. J. Mathar, Mar 06 2010
Binary tree illustration and keyword tabf added by Antti Karttunen, Dec 21 2014

A156552 Unary-encoded compressed factorization of natural numbers.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 8, 7, 6, 9, 16, 11, 32, 17, 10, 15, 64, 13, 128, 19, 18, 33, 256, 23, 12, 65, 14, 35, 512, 21, 1024, 31, 34, 129, 20, 27, 2048, 257, 66, 39, 4096, 37, 8192, 67, 22, 513, 16384, 47, 24, 25, 130, 131, 32768, 29, 36, 71, 258, 1025, 65536, 43, 131072, 2049, 38, 63, 68, 69, 262144
Offset: 1

Views

Author

Leonid Broukhis, Feb 09 2009

Keywords

Comments

The primes become the powers of 2 (2 -> 1, 3 -> 2, 5 -> 4, 7 -> 8); the composite numbers are formed by taking the values for the factors in the increasing order, multiplying them by the consecutive powers of 2, and summing. See the Example section.
From Antti Karttunen, Jun 27 2014: (Start)
The odd bisection (containing even terms) halved gives A244153.
The even bisection (containing odd terms), when one is subtracted from each and halved, gives this sequence back.
(End)
Question: Are there any other solutions that would satisfy the recurrence r(1) = 0; and for n > 1, r(n) = Sum_{d|n, d>1} 2^A033265(r(d)), apart from simple variants 2^k * A156552(n)? See also A297112, A297113. - Antti Karttunen, Dec 30 2017

Examples

			For 84 = 2*2*3*7 -> 1*1 + 1*2 + 2*4 + 8*8 =  75.
For 105 = 3*5*7 -> 2*1 + 4*2 + 8*4 = 42.
For 137 = p_33 -> 2^32 = 4294967296.
For 420 = 2*2*3*5*7 -> 1*1 + 1*2 + 2*4 + 4*8 + 8*16 = 171.
For 147 = 3*7*7 = p_2 * p_4 * p_4 -> 2*1 + 8*2 + 8*4 = 50.

Links

Crossrefs

One less than A005941.
Inverse permutation: A005940 with starting offset 0 instead of 1.
Cf. A000079, A000120, A001222, A052126, A054429, A061395, A064216, A064989, A003188, A243071, A243065-A243066, A244153, A243354, A112798, A125106, A056239, A161511.
Cf. also A297106, A297112 (Möbius transform), A297113, A153013, A290308, A300827, A323243, A323244, A323247, A324201, A324812 (n for which a(n) is a square), A324813, A324822, A324823, A324398, A324713, A324815, A324819, A324865, A324866, A324867.
Other related permutations: A253551, A253792, A253564, A253791, A277195, A297163, A297164, A297165, A297166, A302023, A305418, A322863, A322864.

Programs

  • Mathematica
    Table[Floor@ Total@ Flatten@ MapIndexed[#1 2^(#2 - 1) &, Flatten[ Table[2^(PrimePi@ #1 - 1), {#2}] & @@@ FactorInteger@ n]], {n, 67}] (* Michael De Vlieger, Sep 08 2016 *)
  • PARI
    a(n) = {my(f = factor(n), p2 = 1, res = 0); for(i = 1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p * p2 * (2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); res}; \\ David A. Corneth, Mar 08 2019
  • PARI
    A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
A156552(n) = if(1==n, 0, if(!(n%2), 1+(2*A156552(n/2)), 2*A156552(A064989(n)))); \\ (based on the given recurrence) - Antti Karttunen, Mar 08 2019
  • Perl
    # Program corrected per instructions from Leonid Broukhis. - Antti Karttunen, Jun 26 2014
# However, it gives correct answers only up to n=136, before corruption by a wrap-around effect.
# Note that the correct answer for n=137 is A156552(137) = 4294967296.
$max = $ARGV[0];
$pow = 0;
foreach $i (2..$max) {
@a = split(/ /, `factor $i`);
shift @a;
$shift = 0;
$cur = 0;
while ($n = int shift @a) {
$prime{$n} = 1 << $pow++ if !defined($prime{$n});
$cur |= $prime{$n} << $shift++;
}
print "$cur, ";
}
print "\n";
(Scheme, with memoization-macro definec from Antti Karttunen's IntSeq-library, two different implementations)
(definec (A156552 n) (cond ((= n 1) 0) (else (+ (A000079 (+ -2 (A001222 n) (A061395 n))) (A156552 (A052126 n))))))
(definec (A156552 n) (cond ((= 1 n) (- n 1)) ((even? n) (+ 1 (* 2 (A156552 (/ n 2))))) (else (* 2 (A156552 (A064989 n))))))
;; Antti Karttunen, Jun 26 2014
  • Python
    from sympy import primepi, factorint
def A156552(n): return sum((1<Chai Wah Wu, Mar 10 2023

Formula

From Antti Karttunen, Jun 26 2014: (Start)
a(1) = 0, a(n) = A000079(A001222(n)+A061395(n)-2) + a(A052126(n)).
a(1) = 0, a(2n) = 1+2*a(n), a(2n+1) = 2*a(A064989(2n+1)). [Compare to the entanglement recurrence A243071].
For n >= 0, a(2n+1) = 2*A244153(n+1). [Follows from the latter clause of the above formula.]
a(n) = A005941(n) - 1.
As a composition of related permutations:
a(n) = A003188(A243354(n)).
a(n) = A054429(A243071(n)).
For all n >= 1, A005940(1+a(n)) = n and for all n >= 0, a(A005940(n+1)) = n. [The offset-0 version of A005940 works as an inverse for this permutation.]
This permutations also maps between the partition-lists A112798 and A125106:
A056239(n) = A161511(a(n)). [The sums of parts of each partition (the total sizes).]
A003963(n) = A243499(a(n)). [And also the products of those parts.]
(End)
From Antti Karttunen, Oct 09 2016: (Start)
A161511(a(n)) = A056239(n).
A029837(1+a(n)) = A252464(n). [Binary width of terms.]
A080791(a(n)) = A252735(n). [Number of nonleading 0-bits.]
A000120(a(n)) = A001222(n). [Binary weight.]
For all n >= 2, A001511(a(n)) = A055396(n).
For all n >= 2, A000120(a(n))-1 = A252736(n). [Binary weight minus one.]
A252750(a(n)) = A252748(n).
a(A250246(n)) = A252754(n).
a(A005117(n)) = A277010(n). [Maps squarefree numbers to a permutation of A003714, fibbinary numbers.]
A085357(a(n)) = A008966(n). [Ditto for their characteristic functions.]
For all n >= 0:
a(A276076(n)) = A277012(n).
a(A276086(n)) = A277022(n).
a(A260443(n)) = A277020(n).
(End)
From Antti Karttunen, Dec 30 2017: (Start)
For n > 1, a(n) = Sum_{d|n, d>1} 2^A033265(a(d)). [See comments.]
More linking formulas:
A106737(a(n)) = A000005(n).
A290077(a(n)) = A000010(n).
A069010(a(n)) = A001221(n).
A136277(a(n)) = A181591(n).
A132971(a(n)) = A008683(n).
A106400(a(n)) = A008836(n).
A268411(a(n)) = A092248(n).
A037011(a(n)) = A010052(n) [conjectured, depends on the exact definition of A037011].
A278161(a(n)) = A046951(n).
A001316(a(n)) = A061142(n).
A277561(a(n)) = A034444(n).
A286575(a(n)) = A037445(n).
A246029(a(n)) = A181819(n).
A278159(a(n)) = A124859(n).
A246660(a(n)) = A112624(n).
A246596(a(n)) = A069739(n).
A295896(a(n)) = A053866(n).
A295875(a(n)) = A295297(n).
A284569(a(n)) = A072411(n).
A286574(a(n)) = A064547(n).
A048735(a(n)) = A292380(n).
A292272(a(n)) = A292382(n).
A244154(a(n)) = A048673(n), a(A064216(n)) = A244153(n).
A279344(a(n)) = A279339(n), a(A279338(n)) = A279343(n).
a(A277324(n)) = A277189(n).
A037800(a(n)) = A297155(n).
For n > 1, A033265(a(n)) = 1+A297113(n).
(End)
From Antti Karttunen, Mar 08 2019: (Start)
a(n) = A048675(n) + A323905(n).
a(A324201(n)) = A000396(n), provided there are no odd perfect numbers.
The following sequences are derived from or related to the base-2 expansion of a(n):
A000265(a(n)) = A322993(n).
A002487(a(n)) = A323902(n).
A005187(a(n)) = A323247(n).
A324288(a(n)) = A324116(n).
A323505(a(n)) = A323508(n).
A079559(a(n)) = A323512(n).
A085405(a(n)) = A323239(n).
The following sequences are obtained by applying to a(n) a function that depends on the prime factorization of its argument, which goes "against the grain" because a(n) is the binary code of the factorization of n, which in these cases is then factored again:
A000203(a(n)) = A323243(n).
A033879(a(n)) = A323244(n) = 2*a(n) - A323243(n),
A294898(a(n)) = A323248(n).
A000005(a(n)) = A324105(n).
A000010(a(n)) = A324104(n).
A083254(a(n)) = A324103(n).
A001227(a(n)) = A324117(n).
A000593(a(n)) = A324118(n).
A001221(a(n)) = A324119(n).
A009194(a(n)) = A324396(n).
A318458(a(n)) = A324398(n).
A192895(a(n)) = A324100(n).
A106315(a(n)) = A324051(n).
A010052(a(n)) = A324822(n).
A053866(a(n)) = A324823(n).
A001065(a(n)) = A324865(n) = A323243(n) - a(n),
A318456(a(n)) = A324866(n) = A324865(n) OR a(n),
A318457(a(n)) = A324867(n) = A324865(n) XOR a(n),
A318458(a(n)) = A324398(n) = A324865(n) AND a(n),
A318466(a(n)) = A324819(n) = A323243(n) OR 2*a(n),
A318467(a(n)) = A324713(n) = A323243(n) XOR 2*a(n),
A318468(a(n)) = A324815(n) = A323243(n) AND 2*a(n).
(End)

Extensions

More terms from Antti Karttunen, Jun 28 2014

A003188 Decimal equivalent of Gray code for n.

Original entry on oeis.org

0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8, 24, 25, 27, 26, 30, 31, 29, 28, 20, 21, 23, 22, 18, 19, 17, 16, 48, 49, 51, 50, 54, 55, 53, 52, 60, 61, 63, 62, 58, 59, 57, 56, 40, 41, 43, 42, 46, 47, 45, 44, 36, 37, 39, 38, 34, 35, 33, 32, 96, 97, 99, 98, 102, 103, 101
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Inverse of sequence A006068 considered as a permutation of the nonnegative integers, i.e., A006068(A003188(n)) = n = A003188(A006068(n)). - Howard A. Landman, Sep 25 2001
Restricts to a permutation of each {2^(i - 1) .. 2^i - 1}. - Jason Kimberley, Apr 02 2012
a(n) mod 2 = floor(((n + 1) mod 4) / 2), see also A021913. - Reinhard Zumkeller, Apr 28 2012
Invented by Emile Baudot (1845-1903), originally called a "cyclic-permuted" code. Gray codes are named after Frank Gray, who patented their use for shaft encoders in 1953. [F. Gray, "Pulse Code Communication", U.S. Patent 2,632,058, March 17, 1953.] - Robert G. Wilson v, Jun 22 2014
For n >= 2, let G_n be the graph whose vertices are labeled as 0,1,...,2^n-1, and two vertices are adjacent if and only if their binary expansions differ in exactly one bit, then a(0),a(1),...,a(2^n-1),a(0) is a Hamilton cycle in G_n. - Jianing Song, Jun 01 2022

Examples

			For n = 13, the binary reflected Gray code representation of n is '1011' and 1011_2 = 11_10. So, a(13) = 11. - _Indranil Ghosh_, Jan 23 2017

References

  • M. Gardner, Mathematical Games, Sci. Amer. Vol. 227 (No. 2, Feb. 1972), p. 107.
  • M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 15.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

a(2*A003714(n)) = 3*A003714(n) for all n. - Antti Karttunen, Apr 26 1999
Cf. A014550 (in binary), A055975 (first differences), A048724 (even bisection), A065621 (odd bisection).
Cf. A006068, A038554, A048641, A048642.

Programs

  • C
    int a(int n) { return n ^ (n>>1); }
  • Haskell
    import Data.Bits (xor, shiftR)
a003188 n = n `xor` (shiftR n 1) :: Integer
-- Reinhard Zumkeller, May 26 2013, Apr 28 2012
  • Magma
    // A recursive algorithm
N := 10; s := [[]];
for n in [1..N] do
for j in [#s..1 by -1] do
   Append(~s,Append(s[j],1));
   Append(~s[j],0);
end for;
end for;
[SequenceToInteger(b,2):b in s]; // Jason Kimberley, Apr 02 2012
  • Magma
    // A direct algorithm
I2B := func< i | [b eq 1: b in IntegerToSequence(i,2)]>;
B2I := func< s | SequenceToInteger([b select 1 else 0:b in s],2)>;
[B2I(Xor(I2B(i),I2B(i div 2)cat[false])):i in [1..127]]; //Jason Kimberley, Apr 02 2012
  • Maple
    with(combinat); graycode(6); # to produce first 64 terms
printf(cat(` %.6d`$64), op(map(convert, graycode(6), binary))); lprint(); # to produce binary strings
# alternative:
read("transforms"):
A003188 := proc(n)
    XORnos(n,floor(n/2)) ;
end proc: # R. J. Mathar, Mar 09 2015
# another Maple program:
a:= n-> Bits[Xor](n, iquo(n, 2)):
seq(a(n), n=0..70);  # Alois P. Heinz, Aug 16 2020
  • Mathematica
    f[n_] := BitXor[n, Floor[n/2]]; Array[f, 70, 0] (* Robert G. Wilson v, Jun 09 2010 *)
  • PARI
    a(n)=bitxor(n,n>>1);
  • PARI
    a(n)=sum(k=1,n,(-1)^((k/2^valuation(k,2)-1)/2)*2^valuation(k,2))
  • Python
    def A003188(n):
    return int(bin(n^(n//2))[2:],2) # Indranil Ghosh, Jan 23 2017
  • Python
    def A003188(n): return n^ n>>1 # Chai Wah Wu, Jun 29 2022
  • R
    maxn <- 63 # by choice
a <- 1
for(n in 1:maxn){ a[2*n  ] <- 2*a[n] + (n%%2 != 0)
                  a[2*n+1] <- 2*a[n] + (n%%2 == 0)}
(a <- c(0,a))
# Yosu Yurramendi, Apr 10 2020
(C#)
static uint a(this uint n) => (n >> 1) ^ n; // Frank Hollstein, Mar 12 2021

Formula

a(n) = 2*a(floor(n/2)) + A021913(n - 1). - Henry Bottomley, Apr 05 2001
a(n) = n XOR floor(n/2), where XOR is the binary exclusive OR operator. - Paul D. Hanna, Jun 04 2002
G.f.: (1/(1-x)) * Sum_{k>=0} 2^k*x^2^k/(1 + x^2^(k+1)). - Ralf Stephan, May 06 2003
a(0) = 0, a(2n) = 2a(n) + [n odd], a(2n + 1) = 2a(n) + [n even]. - Ralf Stephan, Oct 20 2003
a(0) = 0, a(n) = 2 a(floor(n/2)) + mod(floor((n + 1)/2), 2).
a(n) = Sum_{k=1..n} 2^A007814(k) * (-1)^((k/2^A007814(k) - 1)/2). - Ralf Stephan, Oct 29 2003
a(0) = 0, a(n + 1) = a(n) XOR 2^A007814(n) - Jaume Simon Gispert (jaume(AT)nuem.com), Sep 11 2004
Inverse of sequence A006068. - Philippe Deléham, Apr 29 2005
a(n) = a(n-1) XOR A006519(n). - Franklin T. Adams-Watters, Jul 18 2011
From Mikhail Kurkov, Sep 27 2023: (Start)
a(2^m + k) = a(2^m - k - 1) + 2^m for 0 <= k < 2^m, m >= 0.
a(n) = a(A053645(A054429(n))) + A053644(n) for n > 0.
a(n) = A063946(a(A053645(n)) + A053644(n)) for n > 0. (End)

A163511 a(0)=1. a(n) = p(A000120(n)) * Product_{m=1..A000120(n)} p(m)^A163510(n,m), where p(m) is the m-th prime.

Original entry on oeis.org

1, 2, 4, 3, 8, 9, 6, 5, 16, 27, 18, 25, 12, 15, 10, 7, 32, 81, 54, 125, 36, 75, 50, 49, 24, 45, 30, 35, 20, 21, 14, 11, 64, 243, 162, 625, 108, 375, 250, 343, 72, 225, 150, 245, 100, 147, 98, 121, 48, 135, 90, 175, 60, 105, 70, 77, 40, 63, 42, 55, 28, 33, 22, 13, 128
Offset: 0

Views

Author

Leroy Quet, Jul 29 2009

Keywords

Comments

This is a permutation of the positive integers.
From Antti Karttunen, Jun 20 2014: (Start)
Note the indexing: the domain starts from 0, while the range excludes zero, thus this is neither a bijection on the set of nonnegative integers nor on the set of positive natural numbers, but a bijection from the former set to the latter.
Apart from that discrepancy, this could be viewed as yet another "entanglement permutation" where the two complementary pairs to be interwoven together are even and odd numbers (A005843/A005408) which are entangled with the complementary pair even numbers (taken straight) and odd numbers in the order they appear in A003961: (A005843/A003961). See also A246375 which has almost the same recurrence.
Note how the even bisection halved gives the same sequence back. (For a(0)=1, take ceiling of 1/2).
(End)
From Antti Karttunen, Dec 30 2017: (Start)
This irregular table can be represented as a binary tree. Each child to the left is obtained by doubling the parent, and each child to the right is obtained by applying A003961 to the parent:
1
|
...................2...................
4 3
8......../ \........9 6......../ \........5
/ \ / \ / \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \
16 27 18 25 12 15 10 7
32 81 54 125 36 75 50 49 24 45 30 35 20 21 14 11
etc.
Sequence A005940 is obtained by scanning the same tree level by level in mirror image fashion. Also in binary trees A253563 and A253565 the terms on level of the tree are some permutation of the terms present on the level n of this tree. A252464(n) gives the distance of n from 1 in all these trees, and A252463 gives the parent of the node containing n.
A252737(n) gives the sum and A252738(n) the product of terms on row n (where 1 is on row 0, 1 on row 1, 3 and 4 on row 2, etc.). A252745(n) gives the number of nodes on level n whose left child is smaller than the right child, and A252744(n) is an indicator function for those nodes.
(End)
Note that the idea behind maps like this (and the mirror image A005940) admits also using alternative orderings of primes, not just standard magnitude-wise ordering (A000040). For example, A332214 is a similar sequence but with primes rearranged as in A332211, and A332817 is obtained when primes are rearranged as in A108546. - Antti Karttunen, Mar 11 2020
From Lorenzo Sauras Altuzarra, Nov 28 2020: (Start)
This sequence is generated from A228351 by applying the following procedure: 1) eliminate the compositions that end in one unless the first one, 2) subtract one unit from every component, 3) replace every tuple [t_1, ..., t_r] by Product_{k=1..r} A000040(k)^(t_k) (see the examples).
Is it true that a(n) = A337909(n+1) if and only if a(n+1) is not a term of A161992?
Does this permutation have any other cycle apart from (1), (2) and (6, 9, 16, 7)? (End)
From Antti Karttunen, Jul 25 2023: (Start)
(In the above question, it is assumed that the starting offset would be 1 instead of 0).
Questions:
Does a(n) = 1+A054429(n) hold only when n is of the form 2^k times 1, 3 or 7, i.e., one of the terms of A029748?
It seems that A007283 gives all fixed points of map n -> a(n), like A335431 seems to give all fixed points of map n -> A332214(n). Is there a general rule for mappings like these that the fixed points (if they exist) must be of the form 2^k times a certain kind of prime, i.e., that any odd composite (times 2^k) can certainly be excluded? See also note in A029747.
(End)
If the conjecture given in A364297 holds, then it implies the above conjecture about A007283. See also A364963. - Antti Karttunen, Sep 06 2023
Conjecture: a(n^k) is never of the form x^k, for any integers n > 0, k > 1, x >= 1. This holds at least for squares, cubes, seventh and eleventh powers (see A365808, A365801, A366287 and A366391). - Antti Karttunen, Sep 24 2023, Oct 10 2023.
See A365805 for why the above holds for any n^k, with k > 1. - Antti Karttunen, Nov 23 2023

Examples

			For n=3, whose binary representation is "11", we have A000120(3)=2, with A163510(3,1) = A163510(3,2) = 0, thus a(3) = p(2) * p(1)^0 * p(2)^0 = 3*1*1 = 3.
For n=9, "1001" in binary, we have A000120(9)=2, with A163510(9,1) = 0 and A163510(9,2) = 2, thus a(9) = p(2) * p(1)^0 * p(2)^2 = 3*1*9 = 27.
For n=10, "1010" in binary, we have A000120(10)=2, with A163510(10,1) = 1 and A163510(10,2) = 1, thus a(10) = p(2) * p(1)^1 * p(2)^1 = 3*2*3 = 18.
For n=15, "1111" in binary, we have A000120(15)=4, with A163510(15,1) = A163510(15,2) = A163510(15,3) = A163510(15,4) = 0, thus a(15) = p(4) * p(1)^0 * p(2)^0 * p(3)^0 * p(4)^0 = 7*1*1*1*1 = 7.
[1], [2], [1,1], [3], [1,2], [2,1] ... -> [1], [2], [3], [1,2], ... -> [0], [1], [2], [0,1], ... -> 2^0, 2^1, 2^2, 2^0*3^1, ... = 1, 2, 4, 3, ... - _Lorenzo Sauras Altuzarra_, Nov 28 2020

Links

Crossrefs

Inverse: A243071.
Cf. A000040, A000120, A000225, A000788, A003961, A007814, A054429, A055396, A064216, A135523, A161992, A163510, A245605, A245612, A246375, A246378, A246681, A161511, A228351, A243499, A243503, A243504, A269854, A280873, A285727, A290251, A293437, A337909.
Cf. A007283 (known positions where a(n)=n), A029747, A029748, A364255 [= gcd(n,a(n))], A364258 [= a(n)-n], A364287 (where a(n) < n), A364292 (where a(n) <= n), A364494 (where n|a(n)), A364496 (where a(n)|n), A364963, A364297.
Cf. A365808 (positions of squares), A365801 (of cubes), A365802 (of fifth powers), A365805 [= A052409(a(n))], A366287, A366391.
Cf. A005940, A332214, A332817, A366275 (variants).

Programs

  • Mathematica
    f[n_] := Reverse@ Map[Ceiling[(Length@ # - 1)/2] &, DeleteCases[Split@ Join[Riffle[IntegerDigits[n, 2], 0], {0}], {k__} /; k == 1]]; {1}~Join~
Table[Function[t, Prime[t] Product[Prime[m]^(f[n][[m]]), {m, t}]][DigitCount[n, 2, 1]], {n, 120}] (* Michael De Vlieger, Jul 25 2016 *)
  • Python
    from sympy import prime
def A163511(n):
    if n:
        k, c, m = n, 0, 1
        while k:
            c += 1
            m *= prime(c)**(s:=(~k&k-1).bit_length())
            k >>= s+1
        return m*prime(c)
    return 1 # Chai Wah Wu, Jul 17 2023

Formula

For n >= 1, a(2n) is even, a(2n+1) is odd. a(2^k) = 2^(k+1), for all k >= 0.
From Antti Karttunen, Jun 20 2014: (Start)
a(0) = 1, a(1) = 2, a(2n) = 2*a(n), a(2n+1) = A003961(a(n)).
As a more general observation about the parity, we have:
For n >= 1, A007814(a(n)) = A135523(n) = A007814(n) + A209229(n). [This permutation preserves the 2-adic valuation of n, except when n is a power of two, in which cases that value is incremented by one.]
For n >= 1, A055396(a(n)) = A091090(n) = A007814(n+1) + 1 - A036987(n).
For n >= 1, a(A000225(n)) = A000040(n).
(End)
From Antti Karttunen, Oct 11 2014: (Start)
As a composition of related permutations:
a(n) = A005940(1+A054429(n)).
a(n) = A064216(A245612(n))
a(n) = A246681(A246378(n)).
Also, for all n >= 0, it holds that:
A161511(n) = A243503(a(n)).
A243499(n) = A243504(a(n)).
(End)
More linking identities from Antti Karttunen, Dec 30 2017: (Start)
A046523(a(n)) = A278531(n). [See also A286531.]
A278224(a(n)) = A285713(n). [Another filter-sequence.]
A048675(a(n)) = A135529(n) seems to hold for n >= 1.
A250245(a(n)) = A252755(n).
A252742(a(n)) = A252744(n).
A245611(a(n)) = A253891(n).
A249824(a(n)) = A275716(n).
A292263(a(n)) = A292264(n). [A292944(n) + A292264(n) = n.]
--
A292383(a(n)) = A292274(n).
A292385(a(n)) = A292271(n). [A292271(n) + A292274(n) = n.]
--
A292941(a(n)) = A292942(n).
A292943(a(n)) = A292944(n).
A292945(a(n)) = A292946(n). [A292942(n) + A292944(n) + A292946(n) = n.]
--
A292253(a(n)) = A292254(n).
A292255(a(n)) = A292256(n). [A292944(n) + A292254(n) + A292256(n) = n.]
--
A279339(a(n)) = A279342(n).
a(A071574(n)) = A269847(n).
a(A279341(n)) = A279338(n).
a(A252756(n)) = A250246(n).
(1+A008836(a(n)))/2 = A059448(n).
(End)
From Antti Karttunen, Jul 26 2023: (Start)
For all n >= 0, a(A007283(n)) = A007283(n).
A001222(a(n)) = A290251(n).
(End)

Extensions

More terms computed and examples added by Antti Karttunen, Jun 20 2014

A006068 a(n) is Gray-coded into n.

Original entry on oeis.org

0, 1, 3, 2, 7, 6, 4, 5, 15, 14, 12, 13, 8, 9, 11, 10, 31, 30, 28, 29, 24, 25, 27, 26, 16, 17, 19, 18, 23, 22, 20, 21, 63, 62, 60, 61, 56, 57, 59, 58, 48, 49, 51, 50, 55, 54, 52, 53, 32, 33, 35, 34, 39, 38, 36, 37, 47, 46, 44, 45, 40, 41, 43, 42, 127, 126, 124, 125, 120, 121
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Equivalently, if binary expansion of n has m bits (say), compute derivative of n (A038554), getting sequence n' of length m-1; sort on n'.
Inverse of sequence A003188 considered as a permutation of the nonnegative integers, i.e., a(A003188(n)) = n = A003188(a(n)). - Howard A. Landman, Sep 25 2001
The sequence exhibits glide reflections that grow fractally. These show up well on the scatterplot, also audibly using the "listen" link. - Peter Munn, Aug 18 2019
Each bit at bit-index k (counted from the right hand end, with the least significant bit having bit-index 0) in the binary representation of a(n) is the parity of the number of 1's among the bits of the binary representation of n that have a bit-index of k or higher. - Frederik P.J. Vandecasteele, May 26 2025

Examples

			The first few values of n' are -,-,1,0,10,11,01,00,100,101,111,110,010,011,001,000,... (for n=0..15) and to put these in lexicographic order we must take n in the order 0,1,3,2,7,6,4,5,15,14,12,13,8,9,11,10,...

References

  • M. Gardner, Mathematical Games, Sci. Amer. Vol. 227 (No. 2, Feb. 1972), p. 107.
  • M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 15.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A038554, A005811, A003188, A014550, A003100, A265263, A377404.
Cf. A054429, A180200. - Reinhard Zumkeller, Aug 15 2010
Cf. A000079, A055975 (first differences), A209281 (binary weight).
A003987, A010060 are used to express relationship between terms of this sequence.

Programs

  • Haskell
    a006068 n = foldl xor 0 $
                  map (div n) $ takeWhile (<= n) a000079_list :: Integer
-- Reinhard Zumkeller, Apr 28 2012
  • Maple
    a:= proc(n) option remember; `if`(n<2, n,
      Bits[Xor](n, a(iquo(n, 2))))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Apr 17 2018
  • Mathematica
    a[n_] := BitXor @@ Table[Floor[n/2^m], {m, 0, Floor[Log[2, n]]}]; a[0]=0; Table[a[n], {n, 0, 69}] (* Jean-François Alcover, Jul 19 2012, after Paul D. Hanna *)
Table[Fold[BitXor, n, Quotient[n, 2^Range[BitLength[n] - 1]]], {n, 0, 70}] (* Jan Mangaldan, Mar 20 2013 *)
  • PARI
    {a(n)=local(B=n);for(k=1,floor(log(n+1)/log(2)),B=bitxor(B,n\2^k));B} /* Paul D. Hanna, Jan 18 2012 */
  • PARI
    /* the following routine needs only O(log_2(n)) operations */
a(n)= {
    my( s=1, ns );
    while ( 1,
        ns = n >> s;
        if ( 0==ns, break() );
        n = bitxor(n, ns);
        s <<= 1;
    );
    return ( n );
} /* Joerg Arndt, Jul 19 2012 */
  • Python
    def a(n):
    s=1
    while True:
        ns=n>>s
        if ns==0: break
        n=n^ns
        s<<=1
    return n
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 07 2017, after PARI code by Joerg Arndt
  • R
    nmax <- 63 # by choice
a <- vector()
for(n in 1:nmax){
  ones <- which(as.integer(intToBits(n)) == 1)
  nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)]
  level <- 0; anbit <- nbit; anbit.s <- nbit
  while(sum(anbit.s) > 0){
    s <- 2^level; if(s > length(anbit.s)) break
    anbit.s <- c(anbit[-(1:s)], rep(0,s))
    anbit <- bitwXor(anbit, anbit.s)
    level <- level + 1
  }
  a <- c(a, sum(anbit*2^(0:(length(anbit) - 1))))
}
(a <- c(0,a))
# Yosu Yurramendi, Oct 12 2021, after PARI code by Joerg Arndt

Formula

a(n) = 2*a(ceiling((n+1)/2)) + A010060(n-1). If 3*2^(k-1) < n <= 2^(k+1), a(n) = 2^(k+1) - 1 - a(n-2^k); if 2^(k+1) < n <= 3*2^k, a(n) = a(n-2^k) + 2^k. - Henry Bottomley, Jan 10 2001
a(n) = n XOR [n/2] XOR [n/4] XOR [n/8] ... XOR [n/2^m] where m = [log(n)/log(2)] (for n>0) and [x] is integer floor of x. - Paul D. Hanna, Jun 04 2002
a(n) XOR [a(n)/2] = n. - Paul D. Hanna, Jan 18 2012
A066194(n) = a(n-1) + 1, n>=1. - Philippe Deléham, Apr 29 2005
a(n) = if n<2 then n else 2*m + (n mod 2 + m mod 2) mod 2, with m=a(floor(n/2)). - Reinhard Zumkeller, Aug 10 2010
a(n XOR m) = a(n) XOR a(m), where XOR is the bitwise exclusive-or operator, A003987. - Peter Munn, Dec 14 2019
a(0) = 0. For all n >= 0 if a(n) is even a(2*n) = 2*a(n), a(2*n+1) = 2*a(n)+1, else a(2*n) = 2*a(n)+1, a(2*n+1) = 2*a(n). - Yosu Yurramendi, Oct 12 2021
Conjecture: a(n) = a(A053645(A063946(n))) + A053644(n) for n > 0 with a(0) = 0. - Mikhail Kurkov, Sep 09 2023
a(n) = 2*A265263(n) - 2*A377404(n) - A010060(n). - Alan Michael Gómez Calderón, Jun 26 2025

Extensions

More terms from Henry Bottomley, Jan 10 2001

A059893 Reverse the order of all but the most significant bit in binary expansion of n: if n = 1ab..yz then a(n) = 1zy..ba.

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 7, 8, 12, 10, 14, 9, 13, 11, 15, 16, 24, 20, 28, 18, 26, 22, 30, 17, 25, 21, 29, 19, 27, 23, 31, 32, 48, 40, 56, 36, 52, 44, 60, 34, 50, 42, 58, 38, 54, 46, 62, 33, 49, 41, 57, 37, 53, 45, 61, 35, 51, 43, 59, 39, 55, 47, 63, 64, 96, 80, 112, 72, 104, 88, 120
Offset: 1

Views

Author

Marc LeBrun, Feb 06 2001

Keywords

Comments

A self-inverse permutation of the natural numbers.
a(n)=n if and only if A081242(n) is a palindrome. - Clark Kimberling, Mar 12 2003
a(n) is the position in B of the reversal of the n-th term of B, where B is the left-to-right binary enumeration sequence (A081242 with the empty word attached as first term). - Clark Kimberling, Mar 12 2003
From Antti Karttunen, Oct 28 2001: (Start)
When certain Stern-Brocot tree-related permutations are conjugated with this permutation, they induce a permutation on Z (folded to N), which is an infinite siteswap permutation (see, e.g., figure 7 in the Buhler and Graham paper, which is permutation A065174). We get:
A065260(n) = a(A057115(a(n))),
A065266(n) = a(A065264(a(n))),
A065272(n) = a(A065270(a(n))),
A065278(n) = a(A065276(a(n))),
A065284(n) = a(A065282(a(n))),
A065290(n) = a(A065288(a(n))). (End)
Every nonnegative integer has a unique representation c(1) + c(2)*2 + c(3)*2^2 + c(4)*2^3 + ..., where every c(i) is 0 or 1. Taking tuples of coefficients in lexical order (i.e., 0, 1; 01,11; 001,011,101,111; ...) yields A059893. - Clark Kimberling, Mar 15 2015
From Ed Pegg Jr, Sep 09 2015: (Start)
The reduced rationals can be ordered either as the Calkin-Wilf tree A002487(n)/A002487(n+1) or the Stern-Brocot tree A007305(n+2)/A047679(n). The present sequence gives the order of matching rationals in the other sequence.
For reference, the Calkin-Wilf tree is 1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4, 1/5, 5/4, 4/7, 7/3, 3/8, 8/5, 5/7, 7/2, 2/7, 7/5, 5/8, 8/3, 3/7, 7/4, 4/5, ..., which is A002487(n)/A002487(n+1).
The Stern-Brocot tree is 1, 1/2, 2, 1/3, 2/3, 3/2, 3, 1/4, 2/5, 3/5, 3/4, 4/3, 5/3, 5/2, 4, 1/5, 2/7, 3/8, 3/7, 4/7, 5/8, 5/7, 4/5, 5/4, 7/5, 8/5, 7/4, 7/3, 8/3, 7/2, ..., which is A007305(n+2)/A047679(n).
There is a great little OEIS-is-useful story here. I had code for the position of fractions in the Calkin-Wilf tree. The best I had for positions of fractions in the Stern-Brocot tree was the paper "Locating terms in the Stern-Brocot tree" by Bruce Bates, Martin Bunder, Keith Tognetti. The method was opaque to me, so I used my Calkin-Wilf code on the Stern-Brocot fractions, and got A059893. And thus the problem was solved. (End)

Examples

			a(11) = a(1011) = 1110 = 14.
With empty word e prefixed, A081242 becomes (e,1,2,11,21,12,22,111,211,121,221,112,...); (reversal of term #9) = (term #12); i.e., a(9)=12 and a(12)=9. - _Clark Kimberling_, Mar 12 2003
From _Philippe Deléham_, Jun 02 2015: (Start)
This sequence regarded as a triangle with rows of lengths 1, 2, 4, 8, 16, ...:
   1;
   2,  3;
   4,  6,  5,  7;
   8, 12, 10, 14,  9,  13,  11,  15;
  16, 24, 20, 28, 18,  26,  22,  30,  17,  25,  21,  29,  19,  27,  23,  31;
  32, 48, 40, 56, 36,  52,  44, ...
Row sums = A010036. (End)

Links

Crossrefs

{A000027, A054429, A059893, A059894} form a 4-group.
The set of permutations {A059893, A080541, A080542} generates an infinite dihedral group.
Cf. A000079, A000523, A007931, A030308.
In other bases: A351702 (balanced ternary), A343150 (Zeckendorf), A343152 (lazy Fibonacci).

Programs

  • Haskell
    a059893 = foldl (\v b -> v * 2 + b) 1 . init . a030308_row
-- Reinhard Zumkeller, May 01 2013
(Scheme, with memoization-macro definec)
(definec (A059893 n) (if (<= n 1) n (let* ((k (- (A000523 n) 1)) (r (A059893 (- n (A000079 k))))) (if (= 2 (floor->exact (/ n (A000079 k)))) (* 2 r) (+ 1 r)))))
;; Antti Karttunen, May 16 2015
  • Maple
    # Implements Bottomley's formula
A059893 := proc(n) option remember; local k; if(1 = n) then RETURN(1); fi; k := floor_log_2(n)-1; if(2 = floor(n/(2^k))) then RETURN(2*A059893(n-(2^k))); else RETURN(1+A059893(n-(2^k))); fi; end;
floor_log_2 := proc(n) local nn,i; nn := n; for i from -1 to n do if(0 = nn) then RETURN(i); fi; nn := floor(nn/2); od; end;
# second Maple program:
a:= proc(n) local i, m, r; m, r:= n, 0;
      for i from 0 while m>1 do r:= 2*r +irem(m,2,'m') od;
      r +2^i
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Feb 28 2015
  • Mathematica
    A059893 = Reap[ For[n=1, n <= 100, n++, a=1; b=n; While[b > 1, a = 2*a + 2*FractionalPart[b/2]; b=Floor[b/2]]; Sow[a]]][[2, 1]] (* Jean-François Alcover, Jul 16 2012, after Harry J. Smith *)
ro[n_]:=Module[{idn=IntegerDigits[n,2]},FromDigits[Join[{First[idn]}, Reverse[ Rest[idn]]],2]]; Array[ro,80] (* Harvey P. Dale, Oct 24 2012 *)
  • PARI
    a(n) = my(b=binary(n)); fromdigits(concat(b[1], Vecrev(vector(#b-1, k, b[k+1]))), 2); \\ Michel Marcus, Sep 29 2021
  • Python
    def a(n): return int('1' + bin(n)[3:][::-1], 2)
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Mar 21 2017
  • R
    maxrow <- 6 # by choice
a <- 1
for(m in 0:maxrow) for(k in 0:(2^m-1)) {
  a[2^(m+1)+    k] <- 2*a[2^m+k]
  a[2^(m+1)+2^m+k] <- 2*a[2^m+k] + 1
}
a
# Yosu Yurramendi, Mar 20 2017
  • R
    maxblock <- 7 # by choice
a <- 1
for(n in 2:2^maxblock){
  ones <- which(as.integer(intToBits(n)) == 1)
  nbit <- as.integer(intToBits(n))[1:tail(ones, n = 1)]
  anbit <- nbit
  anbit[1:(length(anbit) - 1)] <- anbit[rev(1:(length(anbit)-1))]
  a <- c(a, sum(anbit*2^(0:(length(anbit) - 1))))
}
a
# Yosu Yurramendi, Apr 25 2021

Formula

a(n) = A030109(n) + A053644(n). If 2*2^k <= n < 3*2^k then a(n) = 2*a(n-2^k); if 3*2^k <= n < 4*2^k then a(n) = 1 + a(n-2^k) starting with a(1)=1. - Henry Bottomley, Sep 13 2001

A179016 The infinite trunk of binary beanstalk: The only infinite sequence such that a(n-1) = a(n) - number of 1's in binary representation of a(n).

Original entry on oeis.org

0, 1, 3, 4, 7, 8, 11, 15, 16, 19, 23, 26, 31, 32, 35, 39, 42, 46, 49, 53, 57, 63, 64, 67, 71, 74, 78, 81, 85, 89, 94, 97, 101, 104, 109, 112, 116, 120, 127, 128, 131, 135, 138, 142, 145, 149, 153, 158, 161, 165, 168, 173, 176, 180, 184, 190, 193, 197, 200, 205, 209
Offset: 0

Views

Author

Carl R. White, Jun 24 2010

Keywords

Comments

a(n) tells in what number we end in n steps, when we start climbing up the infinite trunk of the "binary beanstalk" from its root (zero). The name "beanstalk" is due to Antti Karttunen.
There are many finite sequences such as 0,1,2; 0,1,3,4,7,9; etc. obeying the same condition (see A218254) and as the length increases, so (necessarily) does the similarity to this infinite sequence.

Links

Crossrefs

Cf. A000120, A010062, A011371, A213710, A213711, A213717, A213730, A213731, A218600, A218616, A218789, A233271, A218602, A054429. First differences: A213712, complement: A213713.
A subsequence of A005187, i.e., a(n) = A005187(A213715(n)). For all n,
A071542(a(n)) = n, and furthermore A213708(n) <= a(n) <= A173601(n). (Cf. A218603, A218604).
Rows of A218254, when reversed, converge towards this sequence.
Cf. A276623, A219648, A219666, A255056, A276573, A276583, A276613 for analogous constructions, and also A259934.

Programs

  • Mathematica
    TakeWhile[Reverse@ NestWhileList[# - DigitCount[#, 2, 1] &, 10^3, # > 0 &], # <= 209 &] (* Michael De Vlieger, Sep 12 2016 *)

Formula

a(0)=0, a(1)=1, and for n > 1, if n = A218600(A213711(n)) then a(n) = (2^A213711(n)) - 1, and in other cases, a(n) = a(n+1) - A213712(n+1). (This formula is based on Carl White's observation that this iterated/converging path must pass through each (2^n)-1. However, it would be very interesting to know whether the sequence admits more traditional recurrence(s), referring to previous, not to further terms in the sequence in their definition!) - Antti Karttunen, Oct 26 2012
a(n) = A218616(A218602(n)). - Antti Karttunen, Mar 04 2013
a(n) = A054429(A233271(A218602(n))). - Antti Karttunen, Dec 12 2013

Extensions

Starting offset changed from 1 to 0 by Antti Karttunen, Nov 05 2012

A080791 Number of nonleading 0's in binary expansion of n.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 1, 0, 3, 2, 2, 1, 2, 1, 1, 0, 4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0, 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1, 4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0, 6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2, 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1, 5, 4, 4, 3, 4, 3, 3, 2, 4
Offset: 0

Views

Author

Cino Hilliard, Mar 25 2003

Keywords

Comments

In this version we consider the number zero to have no nonleading 0's, thus a(0) = 0. The variant A023416 has a(0) = 1.
Number of steps required to reach 1, starting at n + 1, under the operation: if x is even divide by 2 else add 1. This is the x + 1 problem (as opposed to the 3x + 1 problem).

Examples

			a(4) = 2 since 4 in binary is 100, which has two zeros.
a(5) = 1 since 5 in binary is 101, which has only one zero.

Links

Crossrefs

Cf. A000120, A007814, A023416, A029837, A036987, A080791-A080801, A048881, A054429, A092339, A102364, A120511, A233271, A233272, A233273.

Programs

  • Maple
    seq(numboccur(0, Bits[Split](n)), n=0..100); # Robert Israel, Oct 26 2017
  • Mathematica
    {0}~Join~Table[Last@ DigitCount[n, 2], {n, 120}] (* Michael De Vlieger, Mar 07 2016 *)
f[n_] := If[OddQ@ n, f[n -1] -1, f[n/2] +1]; f[0] = f[1] = 0; Array[f, 105, 0] (* Robert G. Wilson v, May 21 2017 *)
Join[{0}, Table[Count[IntegerDigits[n, 2], 0], {n, 1, 100}]] (* Vincenzo Librandi, Oct 27 2017 *)
  • PARI
    a(n)=if(n,a(n\2)+1-n%2)
  • PARI
    A080791(n)=if(n,logint(n,2)+1-hammingweight(n)) \\ M. F. Hasler, Oct 26 2017
  • Python
    def a(n): return bin(n)[2:].count("0") if n>0 else 0 # Indranil Ghosh, Apr 10 2017
  • Scheme
    ;; with memoizing definec-macro from Antti Karttunen's IntSeq-library)
(define (A080791 n) (- (A029837 (+ 1 n)) (A000120 n)))
;; Alternative version based on a simple recurrence:
(definec (A080791 n) (if (zero? n) 0 (+ (A080791 (- n 1)) (A007814 n) (A036987 (- n 1)) -1)))
;; from Antti Karttunen, Dec 12 2013

Formula

From Antti Karttunen, Dec 12 2013: (Start)
a(n) = A029837(n+1) - A000120(n).
a(0) = 0, and for n > 0, a(n) = (a(n-1) + A007814(n) + A036987(n-1)) - 1.
For all n >= 1, a(A054429(n)) = A048881(n-1) = A000120(n) - 1.
Equally, for all n >= 1, a(n) = A000120(A054429(n)) - 1.
(End)
Recurrence: a(2n) = a(n) + 1 (for n > 0), a(2n + 1) = a(n). - Ralf Stephan from Cino Hilliard's PARI program, Dec 16 2013. Corrected by Alonso del Arte, May 21 2017 after consultation with Chai Wah Wu and Ray Chandler, "n > 0" added by M. F. Hasler, Oct 26 2017
a(n) = A023416(n) for all n > 0. - M. F. Hasler, Oct 26 2017
G.f. g(x) satisfies g(x) = (1+x)*g(x^2) + x^2/(1-x^2). - Robert Israel, Oct 26 2017

A243071 Permutation of nonnegative integers: a(1) = 0, a(2) = 1, a(2n) = 2*a(n), a(2n+1) = 1 + 2*a(A064989(2n+1)).

Original entry on oeis.org

0, 1, 3, 2, 7, 6, 15, 4, 5, 14, 31, 12, 63, 30, 13, 8, 127, 10, 255, 28, 29, 62, 511, 24, 11, 126, 9, 60, 1023, 26, 2047, 16, 61, 254, 27, 20, 4095, 510, 125, 56, 8191, 58, 16383, 124, 25, 1022, 32767, 48, 23, 22, 253, 252, 65535, 18, 59, 120, 509, 2046, 131071
Offset: 1

Views

Author

Antti Karttunen, Jun 20 2014

Keywords

Comments

Note the indexing: the domain starts from 1, while the range includes also zero.
See also the comments at A163511, which is the inverse permutation to this one.

Links

Crossrefs

Inverse: A163511.
Cf. A000040, A000225, A007814, A054429, A064989, A064216, A122111, A209229, A245611 (= (a(2n-1)-1)/2, for n > 1), A245612, A292383, A292385, A297171 (Möbius transform).
Cf. A007283 (known positions where a(n)=n), A364256 [= gcd(n,a(n))], A364288 [= n-a(n)], A364289 [where a(n)>=n], A364290 [where a(n)A364291 [where a(n)<=n], A364497 [where n|a(n)].
Cf. A156552 (variant with inverted binary code), A253566, A332215, A332811, A334859 (other variants).

Programs

  • PARI
    A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
A243071(n) = if(n<=2, n-1, if(!(n%2), 2*A243071(n/2), 1+(2*A243071(A064989(n))))); \\ Antti Karttunen, Jul 18 2020
  • PARI
    A243071(n) = if(n<=2, n-1, my(f=factor(n), p, p2=1, res=0); for(i=1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p*p2*(2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); ((3<<#binary(res\2))-res-1)); \\ (Combining programs given in A156552 and A054429) - Antti Karttunen, Jul 28 2023
  • Python
    from functools import reduce
from sympy import factorint, prevprime
from operator import mul
def a064989(n):
    f = factorint(n)
    return 1 if n==1 else reduce(mul, (1 if i==2 else prevprime(i)**f[i] for i in f))
def a(n): return n - 1 if n<3 else 2*a(n//2) if n%2==0 else 1 + 2*a(a064989(n))
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 15 2017
  • Scheme
    ;; With memoizing definec-macro from Antti Karttunen's IntSeq-library.
(definec (A243071 n) (cond ((<= n 2) (- n 1)) ((even? n) (* 2 (A243071 (/ n 2)))) (else (+ 1 (* 2 (A243071 (A064989 n)))))))

Formula

a(1) = 0, a(2) = 1, a(2n) = 2*a(n), a(2n+1) = 1 + 2*a(A064989(2n+1)).
For n >= 1, a(A000040(n)) = A000225(n).
For n >= 1, a(2n+1) = 1 + 2*a(A064216(n+1)).
From Antti Karttunen, Jul 18 2020: (Start)
a(n) = A245611(A048673(n)).
a(n) = A253566(A122111(n)).
a(n) = A334859(A225546(n)).
For n >= 2, a(n) = A054429(A156552(n)).
a(n) = A292383(n) + A292385(n) = A292383(n) OR A292385(n).
For n > 1, A007814(a(n)) = A007814(n) - A209229(n). [This map preserves the 2-adic valuation of n, except when n is a power of two, in which cases it is decremented by one.]
(End)
Previous Showing 11-20 of 214 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.