|
| |
|
|
A005940
|
|
The Doudna sequence: write n-1 in binary; power of p_k in a(n) is # of 1's that are followed by k-1 0's.
(Formerly M0509)
|
|
241
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
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, 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 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
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
A. Karttunen & R. Zumkeller (first 1024 terms), Table of n, a(n) for n = 1..8192
R. E. Kutz, Two unusual sequences, Two-Year College Mathematics Journal, 12 (1981), 316-319.
Index entries for sequences that are permutations of the natural numbers
|
|
|
FORMULA
|
a(n) = f(n-1, 1, 1) with f(n, i, x) = if n=0 then x = else (if n mod 2 = 0 then f(n/2, i+1, x) else f((n-1)/2, i, x*prime(i))). - Reinhard Zumkeller, Aug 23 2006, R. J. Mathar, Mar 06 2010
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)
|
|
|
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 *)
|
|
|
PROG
|
(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
(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
(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
|
|
|
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).
Cf. also A000040, A000120, A000142, A001511, A002110, A002450, A003961, A053645, A055396, A070939, A112798, A163511, A243353, A006068, A054429, A244154, A252463, A252464, A252745, A252750, A250246, A252753, A253552, A253563, A253565, 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.
Sequence in context: A207801 A324106 A252753 * A005941 A269857 A269847
Adjacent sequences: A005937 A005938 A005939 * A005941 A005942 A005943
|
|
|
KEYWORD
|
nonn,easy,nice,tabf,look
|
|
|
AUTHOR
|
N. J. A. Sloane and J. H. Conway
|
|
|
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
|
|
|
STATUS
|
approved
|
| |
|
|
