login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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]. 166
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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)

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Index entries for sequences that are permutations of the natural numbers

FORMULA

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)

EXAMPLE

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.

MAPLE

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

MATHEMATICA

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

PROG

(Haskell)

a048673 = (`div` 2) . (+ 1) . a045965

-- Reinhard Zumkeller, Jul 12 2012

(PARI)

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

(PARI) 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

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

(Python)

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

CROSSREFS

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 A003961 (A045965), A108951, 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.

Sequence in context: A118317 A127522 A254103 * A288119 A292575 A096070

Adjacent sequences:  A048670 A048671 A048672 * A048674 A048675 A048676

KEYWORD

nonn

AUTHOR

Antti Karttunen, Jul 14 1999

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 14 08:31 EDT 2021. Contains 345018 sequences. (Running on oeis4.)