A183209 -id:A183209 - cp's OEIS frontend

A048673 Permutation of natural numbers: a(n) = (A003961(n)+1) / 2 [where A003961(n) shifts the prime factorization of n one step towards larger primes].

1, 2, 3, 5, 4, 8, 6, 14, 13, 11, 7, 23, 9, 17, 18, 41, 10, 38, 12, 32, 28, 20, 15, 68, 25, 26, 63, 50, 16, 53, 19, 122, 33, 29, 39, 113, 21, 35, 43, 95, 22, 83, 24, 59, 88, 44, 27, 203, 61, 74, 48, 77, 30, 188, 46, 149, 58, 47, 31, 158, 34, 56, 138, 365, 60, 98, 36, 86, 73

Offset: 1

Antti Karttunen, Jul 14 1999

nonn

Inverse of sequence A064216 considered as a permutation of the positive integers. - Howard A. Landman, Sep 25 2001
From Antti Karttunen, Dec 20 2014: (Start)
Permutation of natural numbers obtained by replacing each prime divisor of n with the next prime and mapping the generated odd numbers back to all natural numbers by adding one and then halving.
Note: there is a 7-cycle almost right in the beginning: (6 8 14 17 10 11 7). (See also comments at A249821. This 7-cycle is endlessly copied in permutations like A250249/A250250.)
The only 3-cycle in range 1 .. 402653184 is (2821 3460 5639).
For 1- and 2-cycles, see A245449.
(End)
The first 5-cycle is (1410, 2783, 2451, 2703, 2803). - Robert Israel, Jan 15 2015
From Michel Marcus, Aug 09 2020: (Start)
(5194, 5356, 6149, 8186, 10709), (46048, 51339, 87915, 102673, 137205) and (175811, 200924, 226175, 246397, 267838) are other 5-cycles.
(10242, 20479, 21413, 29245, 30275, 40354, 48241) is another 7-cycle. (End)
From Antti Karttunen, Feb 10 2021: (Start)
Somewhat artificially, also this permutation can be represented as a binary tree. Each child to the left is obtained by multiplying the parent by 3 and subtracting one, while each child to the right is obtained by applying A253888 to the parent:
                                       1
                                       |
                    ................../ \..................
                   2                                       3
         5......../ \........4                   8......../ \........6
        / \                 / \                 / \                 / \
       /   \               /   \               /   \               /   \
      /     \             /     \             /     \             /     \
    14       13         11       7          23       9          17       18
  41 10    38  12     32  28   20 15      68  25   26 63      50  16   53  19
etc.
Each node's (> 1) parent can be obtained with A253889. Sequences A292243, A292244, A292245 and A292246 are constructed from the residues (mod 3) of the vertices encountered on the path from n to the root (1).
(End)

			For n = 6, as 6 = 2 * 3 = prime(1) * prime(2), we have a(6) = ((prime(1+1) * prime(2+1))+1) / 2 = ((3 * 5)+1)/2 = 8.
For n = 12, as 12 = 2^2 * 3, we have a(12) = ((3^2 * 5) + 1)/2 = 23.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for sequences that are permutations of the natural numbers.

Inverse: A064216.
Row 1 of A251722, Row 2 of A249822.
One more than A108228, half the terms of A243501.
Fixed points: A048674.
Positions of records: A029744, their values: A246360 (= A007051 interleaved with A057198).
Positions of subrecords: A247283, their values: A247284.
Cf. A246351 (Numbers n such that a(n) < n.)
Cf. A246352 (Numbers n such that a(n) >= n.)
Cf. A246281 (Numbers n such that a(n) <= n.)
Cf. A246282 (Numbers n such that a(n) > n.), A252742 (their char. function)
Cf. A246261 (Numbers n for which a(n) is odd.)
Cf. A246263 (Numbers n for which a(n) is even.)
Cf. A246260 (a(n) reduced modulo 2), A341345 (modulo 3), A341346, A292251 (3-adic valuation), A292252.
Cf. A246342 (Iterates starting from n=12.)
Cf. A246344 (Iterates starting from n=16.)
Cf. also A003602, A003961 (A045965), A108951, A151800, A245449, A249735, A249821, A250471, A250249, A250250.
Cf. A245447 (This permutation "squared", a(a(n)).)
Other permutations whose formulas refer to this sequence: A122111, A243062, A243066, A243500, A243506, A244154, A244319, A245605, A245608, A245610, A245612, A245708, A246265, A246267, A246268, A246363, A249745, A249824, A249826, and also A183209, A254103 that are somewhat similar.
Cf. also prime-shift based binary trees A005940, A163511, A245612 and A244154.
Cf. A253888, A253889, A292243, A292244, A292245 and A292246 for other derived sequences.
Cf. A323893 (Dirichlet inverse), A323894 (sum with it), A336840 (inverse Möbius transform).

a048673 = (`div` 2) . (+ 1) . a045965
-- Reinhard Zumkeller, Jul 12 2012

f:= proc(n)
local F,q,t;
  F:= ifactors(n)[2];
  (1 + mul(nextprime(t[1])^t[2], t = F))/2
end proc:
seq(f(n),n=1..1000); # Robert Israel, Jan 15 2015

Table[(Times @@ Power[If[# == 1, 1, NextPrime@ #] & /@ First@ #, Last@ #] + 1)/2 &@ Transpose@ FactorInteger@ n, {n, 69}] (* Michael De Vlieger, Dec 18 2014, revised Mar 17 2016 *)

A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From A003961
A048673(n) = (A003961(n)+1)/2; \\ Antti Karttunen, Dec 20 2014

A048673(n) = if(1==n,n,if(n%2,A253888(A048673((n-1)/2)),(3*A048673(n/2))-1)); \\ (Not practical, but demonstrates the construction as a binary tree). - Antti Karttunen, Feb 10 2021

from sympy import factorint, nextprime, prod
def a(n):
    f = factorint(n)
    return 1 if n==1 else (1 + prod(nextprime(i)**f[i] for i in f))//2 # Indranil Ghosh, May 09 2017

(define (A048673 n) (/ (+ 1 (A003961 n)) 2)) ;; Antti Karttunen, Dec 20 2014

From Antti Karttunen, Dec 20 2014: (Start)
a(1) = 1; for n>1: If n = product_{k>=1} (p_k)^(c_k), then a(n) = (1/2) * (1 + product_{k>=1} (p_{k+1})^(c_k)).
a(n) = (A003961(n)+1) / 2.
a(n) = floor((A045965(n)+1)/2).
Other identities. For all n >= 1:
a(n) = A108228(n)+1.
a(n) = A243501(n)/2.
A108951(n) = A181812(a(n)).
a(A246263(A246268(n))) = 2*n.
As a composition of other permutations involving prime-shift operations:
a(n) = A243506(A122111(n)).
a(n) = A243066(A241909(n)).
a(n) = A241909(A243062(n)).
a(n) = A244154(A156552(n)).
a(n) = A245610(A244319(n)).
a(n) = A227413(A246363(n)).
a(n) = A245612(A243071(n)).
a(n) = A245608(A245605(n)).
a(n) = A245610(A244319(n)).
a(n) = A249745(A249824(n)).
For n >= 2, a(n) = A245708(1+A245605(n-1)).
(End)
From Antti Karttunen, Jan 17 2015: (Start)
We also have the following identities:
a(2n) = 3*a(n) - 1. [Thus a(2n+1) = 0 or 1 when reduced modulo 3. See A341346]
a(3n) = 5*a(n) - 2.
a(4n) = 9*a(n) - 4.
a(5n) = 7*a(n) - 3.
a(6n) = 15*a(n) - 7.
a(7n) = 11*a(n) - 5.
a(8n) = 27*a(n) - 13.
a(9n) = 25*a(n) - 12.
and in general:
a(x*y) = (A003961(x) * a(y)) - a(x) + 1, for all x, y >= 1.
(End)
From Antti Karttunen, Feb 10 2021: (Start)
For n > 1, a(2n) = A016789(a(n)-1), a(2n+1) = A253888(a(n)).
a(2^n) = A007051(n) for all n >= 0. [A property shared with A183209 and A254103].
(End)
a(n) = A003602(A003961(n)). - Antti Karttunen, Apr 20 2022
Sum_{k=1..n} a(k) ~ c * n^2, where c = (1/4) * Product_{p prime} ((p^2-p)/(p^2-nextprime(p))) = 1.0319981... , where nextprime is A151800. - Amiram Eldar, Jan 18 2023

New name and crossrefs to derived sequences added by Antti Karttunen, Dec 20 2014

A254103 Permutation of natural numbers: a(0) = 0, a(2n) = (3a(n))-1, a(2n+1) = floor((3(1+a(n)))/2).

Original entry on oeis.org

0, 1, 2, 3, 5, 4, 8, 6, 14, 9, 11, 7, 23, 13, 17, 10, 41, 22, 26, 15, 32, 18, 20, 12, 68, 36, 38, 21, 50, 27, 29, 16, 122, 63, 65, 34, 77, 40, 44, 24, 95, 49, 53, 28, 59, 31, 35, 19, 203, 103, 107, 55, 113, 58, 62, 33, 149, 76, 80, 42, 86, 45, 47, 25, 365, 184, 188, 96, 194, 99, 101, 52, 230, 117, 119, 61, 131, 67, 71, 37, 284, 144, 146, 75, 158, 81, 83, 43

Offset: 0

Antti Karttunen, Jan 25 2015

nonn

This sequence can be represented as a binary tree. Each child to the left is obtained by multiplying the parent by three and subtracting one, and each child to the right is obtained by adding one to parent, multiplying by three, and then halving the result (discarding a possible remainder):
                                     0
                                     |
                  ...................1...................
                 2                                       3
       5......../ \........4                   8......../ \........6
      / \                 / \                 / \                 / \
     /   \               /   \               /   \               /   \
    /     \             /     \             /     \             /     \
  14       9          11       7          23       13         17       10
41  22   26 15      32  18   20 12      68  36   38  21     50  27   29  16
etc.

Antti Karttunen, Table of n, a(n) for n = 0..8191
Index entries for sequences that are permutations of the natural numbers

Inverse: A254104.
Cf. A007051, A016789, A032766, A140263, A191450, A246207.
Similar permutations: A048673, A183209.

def a(n):
    if n==0: return 0
    if n%2==0: return 3*a(n//2) - 1
    else: return int((3*(1 + a((n - 1)//2)))/2)
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 06 2017

a(0) = 0, a(2n) = A016789(a(n)-1), a(2n+1) = A032766(1+a(n)).
a(0) = 0, a(2n) = (3*a(n))-1, a(2n+1) = floor((3*(1+a(n)))/2).
Other identities:
a(2^n) = A007051(n) for all n >= 0. [A property shared with A048673 and A183209.]

A183079 Tree generated by the triangular numbers: a(1) = 1; a(2n) = nontriangular(a(n)), a(2n+1) = triangular(a(n+1)), where triangular = A000217, nontriangular = A014132.

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 10, 7, 21, 9, 15, 8, 55, 14, 28, 11, 231, 27, 45, 13, 120, 20, 36, 12, 1540, 65, 105, 19, 406, 35, 66, 16, 26796, 252, 378, 34, 1035, 54, 91, 18, 7260, 135, 210, 26, 666, 44, 78, 17, 1186570, 1595, 2145, 76, 5565, 119, 190, 25, 82621, 434

Offset: 1

Clark Kimberling, Dec 23 2010

A permutation of the positive integers.
In general, suppose that L and U are complementary sequences of positive integers such that
(1) L(1)=1; and
(2) if n>1, then n=L(k) or n=U(k) for some kThe tree generated by the sequence L is defined as follows:
  T(0,0)=1; T(1,0)=2; T(n,2j)=L(T(n-1,j));
  T(n,2j+1)=U(T(n-1,j)); for j=0,1,...,2^(n-1)-1, n>=2.
The numbers, taken in the order generated, form a permutation of the positive integers.

			First levels of the tree:
                                    1
                                    |
                 ...................2...................
                3                                       4
      6......../ \........5                   10......./ \........7
     / \                 / \                 / \                 / \
    /   \               /   \               /   \               /   \
   /     \             /     \             /     \             /     \
  21      9          15       8          55       14         28      11
231 27  45 13     120  20   36 12    1540  65  105  19    406  35  66  16
Beginning with 3 and 4, the numbers are generated in pairs, such as (3,4), (6,5), (10,7), (21,9),...
In all such pairs, the first number belongs to A000217; the second, to A014132.

Reinhard Zumkeller, Rows n = 1..14 of triangle, flattened
Index entries for sequences that are permutations of the natural numbers

Cf. A000217, A014132, A074049.
Cf. A220347 (inverse), A220348.
Cf. A183089, A183209 (similar permutations), also A257798.

a183079 n k = a183079_tabf !! (n-1) !! (k-1)
a183079_row n = a183079_tabf !! n
a183079_tabf = [1] : iterate (\row -> concatMap f row) [2]
   where f x = [a000217 x, a014132 x]
a183079_list = concat a183079_tabf
-- Reinhard Zumkeller, Dec 12 2012

tr[n_]:=n*(n+1)/2; nt[n_]:= n+Round@ Sqrt[2*n];a[1]=1; a[n_Integer] := a[n] = If[ EvenQ@n, nt@a[n/2], tr@ a@ Ceiling[n/2]]; a/@Range[58] (* Giovanni Resta, May 20 2015 *)

;; With memoizing definec-macro.
(definec (A183079 n) (cond ((<= n 1) n) ((even? n) (A014132 (A183079 (/ n 2)))) (else (A000217 (A183079 (/ (+ n 1) 2))))))
;; Antti Karttunen, May 18 2015

Let L(n) be the n-th triangular number (A000217).
Let U(n) be the n-th non-triangular number (A014132).
The tree-array T(n,k) is then given by rows:
T(0,0)=1; T(1,0)=2;
T(n,2j)=L(T(n-1,j));
T(n,2j+1)=U(T(n-1,j));
for j=0,1,...,2^(n-1)-1, n>=2.
a(1) = 1; after which: a(2n) = A014132(a(n)), a(2n+1) = A000217(a(n+1)). - Antti Karttunen, May 20 2015

Formula added to the name and a new tree illustration to the Example section by Antti Karttunen, May 20 2015

A254051 Square array A by downward antidiagonals: A(n,k) = (3 + 3^n(2floor(3*k/2) - 1))/6, n,k >= 1; read as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ...

Original entry on oeis.org

1, 3, 2, 4, 8, 5, 6, 11, 23, 14, 7, 17, 32, 68, 41, 9, 20, 50, 95, 203, 122, 10, 26, 59, 149, 284, 608, 365, 12, 29, 77, 176, 446, 851, 1823, 1094, 13, 35, 86, 230, 527, 1337, 2552, 5468, 3281, 15, 38, 104, 257, 689, 1580, 4010, 7655, 16403, 9842, 16, 44, 113, 311, 770, 2066, 4739, 12029, 22964, 49208, 29525, 18, 47

Offset: 1

L. Edson Jeffery & Antti Karttunen, Jan 24 2015

This is transposed dispersion of (3n-1), starting from its complement A032766 as the first row of square array A(row,col). Please see the transposed array A191450 for references and background discussion about dispersions.

For any odd number x = A135765(row,col), the result after one combined Collatz step (3x+1)/2 -> x (A165355) is found in this array at A(row+1,col).

			The top left corner of the array:
   1,   3,   4,   6,   7,   9,  10,  12,   13,   15,   16,   18,   19,   21
   2,   8,  11,  17,  20,  26,  29,  35,   38,   44,   47,   53,   56,   62
   5,  23,  32,  50,  59,  77,  86, 104,  113,  131,  140,  158,  167,  185
  14,  68,  95, 149, 176, 230, 257, 311,  338,  392,  419,  473,  500,  554
  41, 203, 284, 446, 527, 689, 770, 932, 1013, 1175, 1256, 1418, 1499, 1661
...

Inverse: A254052.
Transpose: A191450.
Row 1: A032766.
Cf. A007051, A057198, A199109, A199113 (columns 1-4).
Cf. A254046 (row index of n in this array, see also A253786), A253887 (column index).
Array A135765(n,k) = 2*A(n,k) - 1.
Other related arrays: A254055, A254101, A254102.
Cf. also A000079, A000244, A003961, A007310, A032766, A002260, A004736, A038722, A165355, A254050.
Related permutations: A048673, A254053, A183209, A249745, A254103, A254104.

In A(n,k)-formulas below, n is the row, and k the column index, both starting from 1:
A(n,k) = (3 + ( A000244(n) * (2*A032766(k) - 1) )) / 6. - Antti Karttunen after L. Edson Jeffery's direct formula for A191450, Jan 24 2015
A(n,k) = A048673(A254053(n,k)). [Alternative formula.]
A(n,k) = (1/2) * (1 + A003961((2^(n-1)) * A254050(k))). [The above expands to this.]
A(n,k) = (1/2) * (1 + (A000244(n-1) * A007310(k))). [Which further reduces to this, equivalent to L. Edson Jeffery's original formula above.]
A(1,k) = A032766(k) and for n > 1: A(n,k) = (3 * A254051(n-1,k)) - 1. [The definition of transposed dispersion of (3n-1).]
A(n,k) = (1+A135765(n,k))/2, or when expressed one-dimensionally, a(n) = (1+A135765(n))/2.
A(n+1,k) = A165355(A135765(n,k)).
As a composition of related permutations. All sequences interpreted as one-dimensional:
a(n) = A048673(A254053(n)). [Proved above.]
a(n) = A191450(A038722(n)). [Transpose of array A191450.]

A183211 First of two trees generated by floor[(3n-1)/2].

Original entry on oeis.org

1, 3, 4, 9, 5, 12, 13, 27, 7, 15, 17, 36, 19, 39, 40, 81, 10, 21, 22, 45, 25, 51, 53, 108, 28, 57, 58, 117, 59, 120, 121, 243, 14, 30, 31, 63, 32, 66, 67, 135, 37, 75, 76, 153, 79, 159, 161, 324, 41, 84, 85, 171, 86, 174, 175, 351, 88, 177

Offset: 1

Clark Kimberling, Dec 30 2010

nonn

This tree grows from (L(1),U(1))=(1,3). The second tree, A183212, grows from (L(2),U(2))=(2,6). Here, L(n)=floor[(3n-1)/2] and U(n)=3n. The two trees are complementary in the sense that every positive integer is in exactly one tree. The sequence formed by taking the terms of this tree in increasing order is A183213. Leftmost branch of this tree: A183207. Rightmost: A000244. See A183170 and A183171 for the two trees generated by the Beatty sequence of sqrt(2).

			First four levels of the tree:
.......................1
.......................3
..............4..................9
............5...12............13....27

Ivan Neretin, Table of n, a(n) for n = 1..8192

Cf. A183170, A183212, A001651, A008585, A183209, A183213.

a = {1, 3}; row = {a[[-1]]}; Do[a = Join[a, row = Flatten[{Quotient[3 # - 1, 2], 3 #} & /@ row]], {n, 5}]; a (* Ivan Neretin, May 25 2015 *)

See the formula at A183209, but use L(n)=floor[(3n-1)/2] and U(n)=3n instead of L(n)=floor(3n/2) and U(n)=3n-1.

A183210 Tree generated by 3n-2.

Original entry on oeis.org

1, 2, 4, 3, 10, 6, 7, 5, 28, 15, 16, 9, 19, 11, 13, 8, 82, 42, 43, 23, 46, 24, 25, 14, 55, 29, 31, 17, 37, 20, 22, 12, 244, 123, 124, 63, 127, 65, 67, 35, 136, 69, 70, 36, 73, 38, 40, 21, 163, 83, 85, 44, 91, 47, 49, 26, 109, 56, 58, 30, 64, 33, 34, 18, 730

Offset: 1

Clark Kimberling, Dec 30 2010

nonn

A permutation of the positive integers. See A183079 and A183209. Leftmost branch: A034472. Rightmost branch: A061419.

Cf. A183079, A034472, A061418, A061419, A016777, A007494.

Let L(n)=3n-2.
Let U(n)=A007494(n); U is the complement of L.
The tree-array T(n,k) is then given by rows:
T(0,0)=1; T(1,0)=2;
T(n,2j)=L(T(n-1),j);
T(n,2j+1)=U(T(n-1),j);
for j=0,1,...,2^(n-1)-1, n>=2.

Showing 1-7 of 7 results.

cp's OEIS Frontend

A259431 Inverse of permutation in A183209.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Mathematica

A048673 Permutation of natural numbers: a(n) = (A003961(n)+1) / 2 [where A003961(n) shifts the prime factorization of n one step towards larger primes].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Scheme

Formula

Extensions

A254103 Permutation of natural numbers: a(0) = 0, a(2n) = (3*a(n))-1, a(2n+1) = floor((3*(1+a(n)))/2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

A183079 Tree generated by the triangular numbers: a(1) = 1; a(2n) = nontriangular(a(n)), a(2n+1) = triangular(a(n+1)), where triangular = A000217, nontriangular = A014132.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Scheme

Formula

Extensions

A254051 Square array A by downward antidiagonals: A(n,k) = (3 + 3^n*(2*floor(3*k/2) - 1))/6, n,k >= 1; read as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ...

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A183211 First of two trees generated by floor[(3n-1)/2].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A183210 Tree generated by 3n-2.

Views

Author

Keywords

Comments

Crossrefs

Formula

A254103 Permutation of natural numbers: a(0) = 0, a(2n) = (3a(n))-1, a(2n+1) = floor((3(1+a(n)))/2).

A254051 Square array A by downward antidiagonals: A(n,k) = (3 + 3^n(2floor(3*k/2) - 1))/6, n,k >= 1; read as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ...