A246363 -id:A246363 - 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

A246364 Permutation of natural numbers: a(n) = A064216(A227413(n)).

Original entry on oeis.org

1, 2, 5, 3, 7, 11, 13, 4, 6, 9, 19, 14, 8, 12, 29, 10, 17, 31, 23, 16, 41, 71, 37, 44, 47, 39, 43, 42, 38, 30, 26, 59, 22, 34, 15, 85, 53, 58, 25, 130, 57, 151, 61, 311, 103, 69, 33, 365, 157, 111, 73, 226, 74, 106, 67, 370, 223, 56, 97, 341, 139, 122, 35, 133, 55, 86, 20, 145, 46, 49, 21, 659, 118, 36, 83, 419, 127, 191, 18

Offset: 1

Antti Karttunen, Aug 26 2014

nonn

After a(2) = 2, the rest of the even bisection contains only terms of A246261. However, some of the terms of A246261 are also found in the odd bisection, while terms of A246263, apart from 2, all reside in the odd bisection of this sequence.

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

Inverse: A246363.
Related or similar permutations: A064216, A227413, A246366, A246368.
Cf. A246261, A246263.

default(primelimit,(2^31)+(2^30));
A002808(n) = { my(k=-1); while( -n + n += -k + k=primepi(n), ); n }; \\ This function from M. F. Hasler
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)};
A064216(n) = A064989((2*n)-1);
A227413(n) = if(1==n, 1, if(!(n%2), prime(A227413(n/2)), A002808(A227413((n-1)/2))));
A246364(n) = A064216(A227413(n));
for(n=1, 4095, write("b246364.txt", n, " ", A246364(n)));

(define (A246364 n) (A064216 (A227413 n)))

a(n) = A064216(A227413(n)).

A246367 Permutation of natural numbers: a(n) = A005940(A135141(n)).

Original entry on oeis.org

1, 2, 4, 3, 8, 5, 6, 7, 9, 11, 16, 15, 10, 25, 21, 27, 12, 33, 14, 13, 45, 35, 18, 75, 63, 81, 49, 99, 22, 55, 32, 39, 135, 105, 125, 225, 30, 189, 243, 147, 20, 297, 50, 65, 165, 17, 42, 117, 405, 315, 375, 675, 54, 175, 567, 729, 441, 77, 24, 891, 66, 245, 195, 495, 51, 275, 28, 351, 1215, 945, 26

Offset: 1

Antti Karttunen, Aug 26 2014

nonn

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

Inverse: A246368.
Cf. A000035, A010051.
Related or similar permutations: A005940, A135141, A246363, A246365.

default(primelimit,(2^31)+(2^30));
A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); t }; \\ Modified from code of M. F. Hasler
A135141(n) = if(1==n, 1, if(isprime(n), 2*A135141(primepi(n)), 1+(2*A135141(n-primepi(n)-1))));
A246367(n) = A005940(A135141(n)); \\ Against the grain...
for(n=1, 10000, write("b246367.txt", n, " ", A246367(n)));

(define (A246367 n) (A005940 (A135141 n)))

a(n) = A005940(A135141(n)).
Other identities:
For all n >= 1, A000035(a(n)) = 1 - A010051(n). [This permutation maps primes to even numbers and nonprimes to odd numbers, in some order, because permutation A135141 has the same property and A005940 preserves the parity].

A246380 Permutation of natural numbers: a(1) = 1, a(2n) = nthcomposite(a(n)), a(2n-1) = nthprime(a(A064989(2n-1)-1)), where nthprime = A000040, nthcomposite = A002808, and A064989(n) shifts the prime factorization of n one step towards smaller primes.

Original entry on oeis.org

1, 4, 2, 9, 7, 6, 23, 16, 3, 14, 13, 12, 43, 35, 17, 26, 37, 8, 101, 24, 5, 22, 19, 21, 53, 62, 83, 51, 79, 27, 233, 39, 191, 54, 149, 15, 103, 134, 11, 36, 47, 10, 151, 34, 41, 30, 29, 33, 73, 75, 241, 86, 113, 114, 89, 72, 1153, 108, 443, 40, 593, 296, 547, 56, 167, 245, 173, 76, 563, 194, 1553, 25

Offset: 1

Antti Karttunen, Aug 29 2014

nonn

Has an infinite number of infinite cycles. See comments in A246379.

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

Inverse: A246379.
Similar or related permutations: A246376, A246378, A246363, A246364, A246366, A246368, A064216, A246682.
Cf. A000035, A000040, A002808, A010051, A064989.

default(primelimit,(2^31)+(2^30));
A002808(n) = { my(k=-1); while( -n + n += -k + k=primepi(n), ); n }; \\ This function from M. F. Hasler
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)};
A246380(n) = if(1==n, 1, if(!(n%2), A002808(A246380(n/2)), prime(A246380(A064989(n)-1))));
for(n=1, 3098, write("b246380.txt", n, " ", A246380(n)));
(Scheme, with memoization-macro definec)
(definec (A246380 n) (cond ((< n 2) n) ((even? n) (A002808 (A246380 (/ n 2)))) (else (A000040 (A246380 (- (A064989 n) 1))))))

a(1) = 1, a(2n) = nthcomposite(a(n)), a(2n-1) = nthprime(a(A064989(2n-1)-1)), where nthprime = A000040, nthcomposite = A002808, and A064989(n) shifts the prime factorization of n one step towards smaller primes.
As a composition of related permutations:
a(n) = A246378(A246376(n)).
Other identities. For all n > 1 the following holds:
A010051(a(n)) = A000035(n). [Maps odd numbers larger than one to primes, and even numbers to composites, in some order. Permutations A246378 & A246682 have the same property].

A246365 Permutation of natural numbers: a(n) = A135141(A005940(n)).

Original entry on oeis.org

1, 2, 4, 3, 8, 5, 7, 9, 6, 17, 19, 11, 39, 35, 25, 15, 16, 13, 23, 33, 29, 37, 75, 27, 95, 87, 61, 55, 767, 45, 83, 67, 10, 21, 47, 71, 159, 143, 139, 51, 319, 175, 639, 287, 251, 263, 247, 135, 527, 239, 199, 447, 105, 115, 991, 119, 1015, 443, 4575, 85, 583, 2175, 1343, 151, 12, 31, 63, 69, 131, 77

Offset: 1

Antti Karttunen, Aug 26 2014

nonn

Even terms occur at the positions 2^n + 1 (A000051), in some order, and the odd terms everywhere else.

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

Inverse: A246366.
Related or similar permutations: A005940, A135141, A246363, A246367.
Cf. A000051, A003961.

default(primelimit,(2^31)+(2^30));
A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); t }; \\ Modified from code of M. F. Hasler
A135141(n) = if(1==n, 1, if(isprime(n), 2*A135141(primepi(n)), 1+(2*A135141(n-primepi(n)-1))));
A246365(n) = A135141(A005940(n));
for(n=1, 10000, write("b246365.txt", n, " ", A246365(n)));

(define (A246365 n) (A135141 (A005940 n)))

a(n) = A135141(A005940(n)).

A246379 Permutation of natural numbers: a(1) = 1, a(p_n) = A003961(1+a(n)), a(c_n) = 2*a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n), and A003961(n) shifts the prime factorization of n one step towards larger primes.

Original entry on oeis.org

1, 3, 9, 2, 21, 6, 5, 18, 4, 42, 39, 12, 11, 10, 36, 8, 15, 84, 23, 78, 24, 22, 7, 20, 72, 16, 30, 168, 47, 46, 189, 156, 48, 44, 14, 40, 17, 144, 32, 60, 45, 336, 13, 94, 92, 378, 41, 312, 96, 88, 28, 80, 25, 34, 288, 64, 120, 90, 81, 672, 133, 26, 188, 184, 756, 82, 135, 624, 192, 176, 83, 56, 49

Offset: 1

Antti Karttunen, Aug 29 2014

nonn

Because 2 is the only even prime, it implies that, apart from a(2)=3, odd numbers occur in odd positions only (along with many even numbers that also occur in odd positions). This in turn implies that each odd composite (A071904) resides in a separate infinite cycle in this permutation, except 9, which is in a finite cycle (2 3 9 4).

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

Inverse: A246380.
Similar or related permutations: A246375, A246377, A246363, A246364, A246365, A246367, A246681.
Cf. A000720, A003961, A010051, A065855, A071904.

default(primelimit, (2^31)+(2^30));
A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ Using code of Michel Marcus
A246379(n) = if(1==n, 1, if(isprime(n), A003961(1+A246379(primepi(n))), 2*A246379(n-primepi(n)-1)));
for(n=1, 10000, write("b246379.txt", n, " ", A246379(n)));
(Scheme, with memoization-macro definec)
(definec (A246379 n) (cond ((< n 2) n) ((= 1 (A010051 n)) (A003961 (+ 1 (A246379 (A000720 n))))) (else (* 2 (A246379 (A065855 n))))))

a(1) = 1, and for n > 1, if A010051(n) = 1 [i.e. when n is a prime], a(n) = A003961(1+a(A000720(n))), otherwise a(n) = 2*a(A065855(n)).
As a composition of related permutations:
a(n) = A246375(A246377(n)).
Other identities. For all n > 1 the following holds:
A000035(a(n)) = A010051(n). [Maps primes to odd numbers > 1, and composites to even numbers, in some order. Permutations A246377 & A246681 have the same property].

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].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Scheme

Formula

Extensions

A246364 Permutation of natural numbers: a(n) = A064216(A227413(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Formula

A246367 Permutation of natural numbers: a(n) = A005940(A135141(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Scheme

Formula

A246380 Permutation of natural numbers: a(1) = 1, a(2n) = nthcomposite(a(n)), a(2n-1) = nthprime(a(A064989(2n-1)-1)), where nthprime = A000040, nthcomposite = A002808, and A064989(n) shifts the prime factorization of n one step towards smaller primes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A246365 Permutation of natural numbers: a(n) = A135141(A005940(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Formula

A246379 Permutation of natural numbers: a(1) = 1, a(p_n) = A003961(1+a(n)), a(c_n) = 2*a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n), and A003961(n) shifts the prime factorization of n one step towards larger primes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula