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

A048674 Fixed points of A048673 and A064216: Numbers n such that if n = product_{k >= 1} (p_k)^(c_k), then Product_{k >= 1} (p_{k+1})^(c_k) = (2*n)-1, where p_k indicates the k-th prime, A000040(k).

Original entry on oeis.org

1, 2, 3, 25, 26, 33, 93, 1034, 970225, 8550146, 325422273, 414690595, 1864797542, 2438037206

Offset: 1

Antti Karttunen, Jul 14 1999

Equally: after 1, numbers n such that, if the prime factorization of 2n-1 = Product_{k >= 1} (p_k)^(c_k) then Product_{k >= 1} (p_{k-1})^(c_k) = n.
Factorization of the initial terms: 1, 2, 3, 5^2, 2*13, 3*11, 3*31, 2*11*47, 5^2*197^2, 2*11*47*8269, 3*11*797*12373, 5*11^2*433*1583, 2*23*59*101*6803, 2*11*53*1201*1741.
The only 3-cycle of permutation A048673 in range 1 .. 402653184 is (2821 3460 5639).
For 2-cycles, take setwise difference of A245449 and this sequence.
Numbers k for which A336853(k) = k-1. - Antti Karttunen, Nov 26 2021

			25 is present, as 2*25 - 1 = 49 = p_4^2, and p_3^2 = 5*5 = 25.
26 is present, as 2*26 - 1 = 51 = 3*17 = p_2 * p_8, and p_1 * p_7 = 2*13 = 26.
Alternatively, as 26 = 2*13 = p_1 * p_7, and ((p_2 * p_8)+1)/2 = ((3*17)+1)/2 = 26 also, thus 26 is present.

Fixed points of permutation pair A048673/A064216.
Positions of zeros in A349573.
Subsequence of the following sequences: A245449, A269860, A319630, A349622, A378980 (see also A379216).
This sequence is also obtained as a setwise difference of the following pairs of sequences: A246281 \ A246351, A246352 \ A246282, A246361 \ A246371, A246372 \ A246362.
Cf. A000040, A003961 (A045965), A064989, A285701, A336853.
Cf. also A348514 (fixed points of map A108228, similar to A048673).

A048673 := n -> (A003961(n)+1)/2;
A048674list := proc(upto_n) local b,i; b := [ ]; for i from 1 to upto_n do if(A048673(i) = i) then b := [ op(b), i ]; fi; od: RETURN(b); end;

Join[{1}, Reap[For[n = 1, n < 10^7, n++, ff = FactorInteger[n]; If[Times @@ Power @@@ (NextPrime[ff[[All, 1]]]^ff[[All, 2]]) == 2 n - 1, Print[n]; Sow[n]]]][[2, 1]]] (* Jean-François Alcover, Mar 04 2016 *)

A003961(n) = { my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); };
isA048674(n) = ((n+n)==(1+A003961(n))); \\ Antti Karttunen, Nov 26 2021

Entry revised and the names in Maple-code cleaned by Antti Karttunen, Aug 25 2014

Terms a(11) - a(14) added by Antti Karttunen, Sep 11-13 2014

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

Original entry on oeis.org

1, 2, 3, 4, 5, 11, 10, 7, 9, 14, 17, 31, 13, 6, 12, 34, 8, 23, 59, 41, 71, 16, 19, 39, 25, 26, 58, 37, 61, 30, 44, 22, 33, 49, 18, 85, 86, 15, 38, 69, 29, 151, 35, 55, 42, 107, 57, 97, 106, 21, 191, 122, 53, 111, 134, 74, 145, 109, 46, 82, 89, 50, 47, 36, 157, 133, 121, 43, 92, 110, 68, 52, 131, 28

Offset: 1

Antti Karttunen, Jul 22 2014

nonn

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

Inverse: A245447.
Fixed points: A245449.
Cf. A064216, A243501, A243502.

(define (A245448 n) (A064216 (A064216 n)))

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

For all n >= 1, A243502(n) = A243501(a(n)).

A245447 Permutation of natural numbers: a(n) = A048673(A048673(n)).

Original entry on oeis.org

1, 2, 3, 4, 5, 14, 8, 17, 9, 7, 6, 15, 13, 10, 38, 22, 11, 35, 23, 122, 50, 32, 18, 86, 25, 26, 138, 74, 41, 30, 12, 101, 33, 16, 43, 64, 28, 39, 24, 81, 20, 45, 68, 31, 176, 59, 63, 171, 34, 62, 203, 72, 53, 239, 44, 76, 47, 27, 19, 125, 29, 149, 218, 277, 158, 182, 113, 71, 40

Offset: 1

Antti Karttunen, Jul 22 2014

nonn

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

Inverse: A245448.
Fixed points: A245449.
Cf. A048673, A243501, A243502.

b[p_?PrimeQ] := b[p] = Prime[PrimePi[p] + 1]; b[1] = 1; b[n_] := b[n] = Times @@ (b[First[#]]^Last[#]&) /@ FactorInteger[n];
A048673[n_] := (b[n] + 1)/2;
a[n_] := A048673[A048673[n]];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, May 16 2017 *)

(define (A245447 n) (A048673 (A048673 n)))

a(n) = A048673(A048673(n)).
a(n) = (1/2) * (1 + A003961((1/2) * (1+A003961(n)))). [Where A003961(n) shifts the prime factorization of n one step left.]
a(n) = ((A003961(A243501(n)/2)) + 1) / 2  = ((A003961(A243501(n))/3) + 1) / 2.
For all n >= 1, A243501(n) = A243502(a(n)).

A270430 Numbers n such that A048673(n) and A064216(n) are of the same parity.

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 9, 10, 12, 13, 16, 17, 20, 25, 26, 27, 29, 30, 31, 32, 33, 34, 36, 37, 39, 40, 41, 42, 48, 49, 50, 52, 53, 58, 62, 64, 65, 68, 69, 74, 75, 77, 80, 81, 82, 85, 90, 93, 97, 98, 99, 100, 101, 102, 104, 105, 106, 108, 109, 111, 113, 114, 116, 117, 120, 121, 124, 125, 126, 128, 130, 132, 133, 136, 137, 139, 141, 144

Offset: 1

Antti Karttunen, Mar 17 2016

nonn

See A270434 for the possible bias favoring this sequence over the complement A270431.

Antti Karttunen, Table of n, a(n) for n = 1..17000

Complement: A270431.
Left inverse: A270432.
Cf. A245449 (a subsequence).
Cf. A000035, A048673, A064216, A270434.
Cf. also A269860.

f[n_] := (Times @@ Power[If[# == 1, 1, NextPrime@ #] & /@ First@ #, Last@ #] + 1)/2 &@ Transpose@ FactorInteger@ n; g[n_] := Times @@ Power[If[# == 1, 1, NextPrime[#, -1]] & /@ First@ #, Last@ #] &@ Transpose@ FactorInteger[2 n - 1]; Select[Range@ 144, Xor[EvenQ@ f@ #, OddQ@ g@ #] &] (* Michael De Vlieger, Mar 17 2016 *)

Other identities. For all n >= 1:

A270432(a(n)) = n.

A247283 Positions of subrecords in A048673.

Original entry on oeis.org

5, 7, 9, 15, 18, 27, 36, 54, 72, 108, 144, 216, 288, 432, 576, 864, 1152, 1728, 2304, 3456, 4608, 6912, 9216, 13824, 18432, 27648, 36864, 55296, 73728, 110592, 147456, 221184, 294912, 442368, 589824, 884736, 1179648, 1769472, 2359296, 3538944, 4718592, 7077888

Offset: 1

Antti Karttunen, Sep 11 2014

nonn

Odd bisection seems to be A116453 (i.e. A005010, 9*2^n from a(3)=9 onward).

After terms 7 and 15, even bisection from a(6)=27 onward seems to be A175806 (27*2^n).

			The fourth (A246360(4) = 5) and the fifth (A246360(5) = 8) record of A048673 (1, 2, 3, 5, 4, 8, ...) occur at A029744(4) = 4 and A029744(5) = 6 respectively. In range between, the maximum must occur at 5, thus a(4-3) = a(1) = 5. (All the previous records of A048673 are in consecutive positions, 1, 2, 3, 4, thus there are no previous subrecords).
The ninth (A246360(9) = 68) and the tenth (A246360(10) = 122) record of A048673 occur at A029744(9) = 24 and A029744(10) = 32 respectively. For n in range 25 .. 31 the values of A048673 are: 25, 26, 63, 50, 16, 53, 19, of which 63 is the maximum, and because it occurs at n = 27, we have a(9-3) = a(6) = 27.

Antti Karttunen, Table of n, a(n) for n = 1..60

A247284 gives the corresponding values.

Cf. A005010 (A116453), A175806, A029744, A048673, A064216, A246360, A245449.

\\ Compute A245449, A246360, A247283 and A247284 at the same time:
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); \\ From Michel Marcus
A048673(n) = (A003961(n)+1)/2;
n = 0; i2 = 0; i3 = 0; ir = 0; prevmax = 0; submax = 0; while(n < 2^32, n++; a_n = A048673(n); if((A048673(a_n) == n), i2++; write("b245449.txt", i2, " ", n)); if((a_n > prevmax), if(submax > 0, i3++; write("b247283.txt", i3, " ", submaxpt); write("b247284.txt", i3, " ", submax)); prevmax = a_n; submax = 0; ir++; write("b029744_empirical.txt", ir, " ", n); write("b246360_empirical.txt", ir, " ", a_n), if((a_n > submax), submax = a_n; submaxpt = n)));

(definec (A247283 n) (max_pt_in_range A048673 (+ (A029744 (+ n 3)) 1) (- (A029744 (+ n 4)) 1)))
(define (max_pt_in_range intfun lowlim uplim) (let loop ((i (+ 1 lowlim)) (maxnow (intfun lowlim)) (maxpt lowlim)) (cond ((> i uplim) maxpt) (else (let ((v (intfun i))) (if (> v maxnow) (loop (+ 1 i) v i) (loop (+ 1 i) maxnow maxpt)))))))

a(n) = A064216(A247284(n)).
Conjectures from Chai Wah Wu, Jul 30 2020: (Start)
a(n) = 2*a(n-2) for n > 6.
G.f.: x*(3*x^5 - x^3 + x^2 - 7*x - 5)/(2*x^2 - 1). (End)

A285701 a(n) = number of iterations x -> A064216(x) needed to reach a nonprime number when starting from n, a(2) = a(3) = 1.

Original entry on oeis.org

0, 1, 1, 0, 1, 0, 2, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 3, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Antti Karttunen, Apr 26 2017

nonn

			For n=2, A064216(2) = 2, thus there is exactly one distinct prime that can be reached when iterating A064216 starting from 2, thus a(2) = 1.
For n=19, A064216(19) = 31 (a prime), A064216(31) = 59 (a prime) and A064216(59) = 44 (not a prime), thus there are exactly three distinct primes that are encountered when iterating A064216 starting from 19 before a nonprime is reached, thus a(19) = 3 (the count includes also the starting prime 19).

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A000040, A000720, A010051, A048674, A064216, A064989, A245449, A246373, A285700, A285706.

Cf. A005382 (gives positions of terms > 1 from its third term 7 onward).

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);
A285701(n) = if(!isprime(n),0,if((2==n)||(3==n),1,1+A285701(A064216(n))));

(definec (A285701 n) (cond ((zero? (A010051 n)) 0) ((or (= 2 n) (= 3 n)) 1) (else (+ 1 (A285701 (A064216 n))))))
;; Another version not requiring A064216 and A064989:
(definec (A285701 n) (cond ((zero? (A010051 n)) 0) ((or (= 2 n) (= 3 n)) 1) ((zero? (A010051 (+ n n -1))) 1) (else (+ 1 (A285701 (A000040 (+ -1 (A000720 (+ n n -1)))))))))

If A010051(n) = 0 [when n is a nonprime], a(n) = 0, otherwise a(n) = 1 + a(A064216(n)), with a(2) = a(3) = 1.

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

A048674 Fixed points of A048673 and A064216: Numbers n such that if n = product_{k >= 1} (p_k)^(c_k), then Product_{k >= 1} (p_{k+1})^(c_k) = (2*n)-1, where p_k indicates the k-th prime, A000040(k).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

A245447 Permutation of natural numbers: a(n) = A048673(A048673(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A270430 Numbers n such that A048673(n) and A064216(n) are of the same parity.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A247283 Positions of subrecords in A048673.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Scheme

Formula

A285701 a(n) = number of iterations x -> A064216(x) needed to reach a nonprime number when starting from n, a(2) = a(3) = 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs