A249734 -id:A249734 - cp's OEIS frontend

A003961 Completely multiplicative with a(prime(k)) = prime(k+1).

1, 3, 5, 9, 7, 15, 11, 27, 25, 21, 13, 45, 17, 33, 35, 81, 19, 75, 23, 63, 55, 39, 29, 135, 49, 51, 125, 99, 31, 105, 37, 243, 65, 57, 77, 225, 41, 69, 85, 189, 43, 165, 47, 117, 175, 87, 53, 405, 121, 147, 95, 153, 59, 375, 91, 297, 115, 93, 61, 315, 67, 111, 275, 729, 119

Offset: 1

Marc LeBrun

Meyers (see Guy reference) conjectures that for all r >= 1, the least odd number not in the set {a(i): i < prime(r)} is prime(r+1). - N. J. A. Sloane, Jan 08 2021
Meyers' conjecture would be refuted if and only if for some r there were such a large gap between prime(r) and prime(r+1) that there existed a composite c for which prime(r) < c < a(c) < prime(r+1), in which case (by Bertrand's postulate) c would necessarily be a term of A246281. - Antti Karttunen, Mar 29 2021
a(n) is odd for all n and for each odd m there exists a k with a(k) = m (see A064216). a(n) > n for n > 1: bijection between the odd and all numbers. - Reinhard Zumkeller, Sep 26 2001
a(n) and n have the same number of distinct primes with (A001222) and without multiplicity (A001221). - Michel Marcus, Jun 13 2014
From Antti Karttunen, Nov 01 2019: (Start)
More generally, a(n) has the same prime signature as n, A046523(a(n)) = A046523(n). Also A246277(a(n)) = A246277(n) and A287170(a(n)) = A287170(n).
Many permutations and other sequences that employ prime factorization of n to encode either polynomials, partitions (via Heinz numbers) or multisets in general can be easily defined by using this sequence as one of their constituent functions. See the last line in the Crossrefs section for examples.
(End)

			a(12) = a(2^2 * 3) = a(prime(1)^2 * prime(2)) = prime(2)^2 * prime(3) = 3^2 * 5 = 45.
a(A002110(n)) = A002110(n + 1) / 2.

Richard K. Guy, editor, Problems From Western Number Theory Conferences, Labor Day, 1983, Problem 367 (Proposed by Leroy F. Meyers, The Ohio State U.).

Indranil Ghosh, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Index entries for sequences computed from indices in prime factorization.
Index entries for sequences related to Heinz numbers.

See A045965 for another version.
Row 1 of table A242378 (which gives the "k-th powers" of this sequence), row 3 of A297845 and of A306697. See also arrays A066117, A246278, A255483, A308503, A329050.
Cf. A064989 (a left inverse), A064216, A000040, A002110, A000265, A027746, A046523, A048673 (= (a(n)+1)/2), A108228 (= (a(n)-1)/2), A191002 (= a(n)*n), A252748 (= a(n)-2n), A286385 (= a(n)-sigma(n)), A283980 (= a(n)*A006519(n)), A341529 (= a(n)*sigma(n)), A326042, A049084, A001221, A001222, A122111, A225546, A260443, A245606, A244319, A246269 (= A065338(a(n))), A322361 (= gcd(n, a(n))), A305293.
Cf. A191555, A252738.
Cf. A249734, A249735 (bisections).
Cf. A246261 (a(n) is of the form 4k+1), A246263 (of the form 4k+3), A246271, A246272, A246259, A246281 (n such that a(n) < 2n), A246282 (n such that a(n) > 2n), A252742.
Cf. A275717 (a(n) > a(n-1)), A275718 (a(n) < a(n-1)).
Cf. A003972 (Möbius transform), A003973 (Inverse Möbius transform), A318321.
Cf. A300841, A305421, A322991, A250469, A269379 for analogous shift-operators in other factorization and quasi-factorization systems.
Cf. also following permutations and other sequences that can be defined with the help of this sequence: A005940, A163511, A122111, A260443, A206296, A265408, A265750, A275733, A275735, A297845, A091202 & A091203, A250245 & A250246, A302023 & A302024, A302025 & A302026.
A version for partition numbers is A003964, strict A357853.
A permutation of A005408.
Applying the same transformation again gives A357852.
Other multiplicative sequences: A064988, A357977, A357978, A357980, A357983.
A056239 adds up prime indices, row-sums of A112798.
Cf. A000720, A076610, A296150.

a003961 1 = 1
a003961 n = product $ map (a000040 . (+ 1) . a049084) $ a027746_row n
-- Reinhard Zumkeller, Apr 09 2012, Oct 09 2011
(MIT/GNU Scheme, with Aubrey Jaffer's SLIB Scheme library)
(require 'factor)
(define (A003961 n) (apply * (map A000040 (map 1+ (map A049084 (factor n))))))
;; Antti Karttunen, May 20 2014

a:= n-> mul(nextprime(i[1])^i[2], i=ifactors(n)[2]):
seq(a(n), n=1..80);  # Alois P. Heinz, Sep 13 2017

a[p_?PrimeQ] := a[p] = Prime[ PrimePi[p] + 1]; a[1] = 1; a[n_] := a[n] = Times @@ (a[#1]^#2& @@@ FactorInteger[n]); Table[a[n], {n, 1, 65}] (* Jean-François Alcover, Dec 01 2011, updated Sep 20 2019 *)
Table[Times @@ Map[#1^#2 & @@ # &, FactorInteger[n] /. {p_, e_} /; e > 0 :> {Prime[PrimePi@ p + 1], e}] - Boole[n == 1], {n, 65}] (* Michael De Vlieger, Mar 24 2017 *)

a(n)=local(f); if(n<1,0,f=factor(n); prod(k=1,matsize(f)[1],nextprime(1+f[k,1])^f[k,2]))

a(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ Michel Marcus, May 17 2014

use ntheory ":all";  sub a003961 { vecprod(map { next_prime($) } factor(shift)); }  # _Dana Jacobsen, Mar 06 2016

from sympy import factorint, prime, primepi, prod
def a(n):
    f=factorint(n)
    return 1 if n==1 else prod(prime(primepi(i) + 1)**f[i] for i in f)
[a(n) for n in range(1, 11)] # Indranil Ghosh, May 13 2017

If n = Product p(k)^e(k) then a(n) = Product p(k+1)^e(k).
Multiplicative with a(p^e) = A000040(A000720(p)+1)^e. - David W. Wilson, Aug 01 2001
a(n) = Product_{k=1..A001221(n)} A000040(A049084(A027748(n,k))+1)^A124010(n,k). - Reinhard Zumkeller, Oct 09 2011 [Corrected by Peter Munn, Nov 11 2019]
A064989(a(n)) = n and a(A064989(n)) = A000265(n). - Antti Karttunen, May 20 2014 & Nov 01 2019
A001221(a(n)) = A001221(n) and A001222(a(n)) = A001222(n). - Michel Marcus, Jun 13 2014
From Peter Munn, Oct 31 2019: (Start)
a(n) = A225546((A225546(n))^2).
a(A225546(n)) = A225546(n^2).
(End)
Sum_{k=1..n} a(k) ~ c * n^2, where c = (1/2) * Product_{p prime} ((p^2-p)/(p^2-nextprime(p))) = 2.06399637... . - Amiram Eldar, Nov 18 2022

A246278 Prime shift array: Square array read by antidiagonals: A(1,col) = 2*col, and for row > 1, A(row,col) = A003961(A(row-1,col)).

Original entry on oeis.org

2, 4, 3, 6, 9, 5, 8, 15, 25, 7, 10, 27, 35, 49, 11, 12, 21, 125, 77, 121, 13, 14, 45, 55, 343, 143, 169, 17, 16, 33, 175, 91, 1331, 221, 289, 19, 18, 81, 65, 539, 187, 2197, 323, 361, 23, 20, 75, 625, 119, 1573, 247, 4913, 437, 529, 29, 22, 63, 245, 2401, 209, 2873, 391, 6859, 667, 841, 31

Offset: 2

Antti Karttunen, Aug 21 2014

The array is read by antidiagonals: A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), etc.
This array can be obtained by taking every second column from array A242378, starting from its column 2.
Permutation of natural numbers larger than 1.
The terms on row n are all divisible by n-th prime, A000040(n).
Each column is strictly growing, and the terms in the same column have the same prime signature.
A055396(n) gives the row number of row where n occurs,
and A246277(n) gives its column number, both starting from 1.
From Antti Karttunen, Jan 03 2015: (Start)
A252759(n) gives their sum minus one, i.e. the Manhattan distance of n from the top left corner.
If we assume here that a(1) = 1 (but which is not explicitly included because outside of the array), then A252752 gives the inverse permutation. See also A246276.
(End)

			The top left corner of the array:
   2,     4,     6,     8,    10,    12,    14,    16,    18, ...
   3,     9,    15,    27,    21,    45,    33,    81,    75, ...
   5,    25,    35,   125,    55,   175,    65,   625,   245, ...
   7,    49,    77,   343,    91,   539,   119,  2401,   847, ...
  11,   121,   143,  1331,   187,  1573,   209, 14641,  1859, ...
  13,   169,   221,  2197,   247,  2873,   299, 28561,  3757, ...

Antti Karttunen, Table of n, a(n) for n = 2..1276; the first 50 antidiagonals of the array

First row: A005843 (the even numbers), from 2 onward.
Row 2: A249734, Row 3: A249827.
Column 1: A000040 (primes), Column 2: A001248 (squares of primes), Column 3: A006094 (products of two successive primes), Column 4: A030078 (cubes of primes).
Transpose: A246279.
Inverse permutation: A252752.
One more than A246275.
Cf. A005940, A242378, A246259, A000040, A002260, A004736, A003961, A055396, A083221, A114537, A246277 (terms of A348717 halved), A246675, A246684, A249818, A252759, A253515.
Arrays obtained by applying a particular function (given in parentheses) to the entries of this array. Cases where the columns grow monotonically are indicated with *: A249822 (A078898), A253551 (* A156552), A253561 (* A122111), A341605 (A017665), A341606 (A017666), A341607 (A006530 o A017666), A341608 (A341524), A341626 (A341526), A341627 (A341527), A341628 (A006530 o A341527), A342674 (A341530), A344027 (* A003415, arithmetic derivative), A355924 (A342671), A355925 (A009194), A355926 (A355442), A355927 (* sigma), A356155 (* A258851), A372562 (A252748), A372563 (A286385), A378979 (* deficiency, A033879), A379008 (* (probably), A294898), A379010 (* A000010, Euler phi), A379011 (* A083254).
Cf. A329050 (subtable).

f[p_?PrimeQ] := f[p] = Prime[PrimePi@ p + 1]; f[1] = 1; f[n_] := f[n] = Times @@ (f[First@ #]^Last@ # &) /@ FactorInteger@ n; Block[{lim = 12}, Table[#[[n - k, k]], {n, 2, lim}, {k, n - 1, 1, -1}] &@ NestList[Map[f, #] &, Table[2 k, {k, lim}], lim]] // Flatten (* Michael De Vlieger, Jan 04 2016, after Jean-François Alcover at A003961 *)

(define (A246278 n) (if (<= n 1) n (A246278bi (A002260 (- n 1)) (A004736 (- n 1))))) ;; Square array starts with offset=2, and we have also tacitly defined a(1) = 1 here.
(define (A246278bi row col) (if (= 1 row) (* 2 col) (A003961 (A246278bi (- row 1) col))))

A(1,col) = 2*col, and for row > 1, A(row,col) = A003961(A(row-1,col)).
As a composition of other similar sequences:
a(n) = A122111(A253561(n)).
a(n) = A249818(A083221(n)).
For all n >= 1, a(n+1) = A005940(1+A253551(n)).
A(n, k) = A341606(n, k) * A355925(n, k). - Antti Karttunen, Jul 22 2022

Starting offset of the linear sequence changed from 1 to 2, without affecting the column and row indices by Antti Karttunen, Jan 03 2015

A249824 Permutation of natural numbers: a(n) = A078898(A003961(A003961(2*n))).

Original entry on oeis.org

1, 2, 3, 9, 4, 12, 5, 42, 17, 19, 6, 59, 7, 22, 26, 209, 8, 82, 10, 92, 31, 29, 11, 292, 41, 32, 115, 109, 13, 129, 14, 1042, 40, 39, 48, 409, 15, 49, 45, 459, 16, 152, 18, 142, 180, 52, 20, 1459, 57, 202, 54, 159, 21, 572, 63, 542, 68, 62, 23, 642, 24, 69, 213

Offset: 1

Antti Karttunen, Nov 06 2014

nonn

			a(4) = 9 because of the following. 2n = 2*4 = 8 = 2^3. We replace the prime factor 2 of 8 with the next prime 3 to get 3^3, then replace 3 with 5 to get 5^3 = 125. The smallest prime factor of 125 is 5. 125 is the 9th term of A084967: 5, 25, 35, 55, 65, 85, 95, 115, 125, ..., thus a(4) = 9.

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

Inverse: A249823.
Row 3 of A249822.
Cf. A003961, A048673, A078898, A084967, A243071, A246278, A249734, A249746, A249826, A250475, A275716.
Cf. also A273664, A273669.

t = PositionIndex[FactorInteger[#][[1, 1]] & /@ Range[10^4]]; f[n_] := Times @@ Power[If[# == 1, 1, NextPrime@ #] & /@ First@ #, Last@ #] &@ Transpose@ FactorInteger@ n; Flatten@ Table[Position[Lookup[t, FactorInteger[#][[1, 1]] ], #] &[f@ f[2 n]], {n, 120}] (* Michael De Vlieger, Jul 25 2016, Version 10 *)

(define (A249824 n) (A078898 (A003961 (A003961 (* 2 n)))))

a(n) = A078898(A003961(A003961(2*n))) = A078898(A003961(A249734(n))).
a(n) = A078898(A246278(3,n)).
As a composition of other permutations:
a(n) = A249746(A048673(n)).
a(n) = A250475(A249826(n)).
a(n) = A275716(A243071(n)).
Other identities. For all n >= 1:
a(2n) = A273669(a(n)) and a(A003961(n)) = A273664(a(n)). -- Antti Karttunen, Aug 07 2016

A249735 Odd bisection of A003961: Replace in 2n-1 each prime factor p(k) with prime p(k+1).

Original entry on oeis.org

1, 5, 7, 11, 25, 13, 17, 35, 19, 23, 55, 29, 49, 125, 31, 37, 65, 77, 41, 85, 43, 47, 175, 53, 121, 95, 59, 91, 115, 61, 67, 275, 119, 71, 145, 73, 79, 245, 143, 83, 625, 89, 133, 155, 97, 187, 185, 161, 101, 325, 103, 107, 385, 109, 113, 205, 127, 203, 425, 209, 169, 215, 343, 131, 235, 137, 253, 875, 139, 149, 265, 221, 217, 605, 151

Offset: 1

Antti Karttunen, Nov 23 2014

nonn

This has the same terms as A007310 (Numbers congruent to 1 or 5 mod 6), but in different order. Apart from 1, they are the numbers that occur below the first two rows of arrays like A246278 and A083221 (A083140).

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

Cf. A249734 (the other bisection of A003961).

Cf. also A007310 (A038179), A249746.

(define (A249735 n) (A003961 (+ n n -1)))

a(n) = A003961(2n - 1).
a(n) = A007310(A249746(n)). [Permutation of A007310, Numbers congruent to 1 or 5 mod 6.]
Other identities. For all n >= 1:
A007310(n) = a(A249745(n)).
A246277(5*a(A048673(n))) = n.
A246277(5*a(n)) = A064216(n).

A118306 If n = product{k>=1} p(k)^b(n,k), where p(k) is the k-th prime and where each b(n,k) is a nonnegative integer, then: If n occurs earlier in the sequence, then a(n) = product{k>=2} p(k-1)^b(n,k); If n does not occur earlier in the sequence, then a(n) = product{k>=1} p(k+1)^b(n,k).

Original entry on oeis.org

1, 3, 2, 9, 7, 15, 5, 27, 4, 21, 13, 45, 11, 33, 6, 81, 19, 75, 17, 63, 10, 39, 29, 135, 49, 51, 8, 99, 23, 105, 37, 243, 14, 57, 77, 225, 31, 69, 22, 189, 43, 165, 41, 117, 12, 87, 53, 405, 25, 147, 26, 153, 47, 375, 91, 297, 34, 93, 61, 315, 59, 111, 20, 729, 119, 195, 71

Offset: 1

Leroy Quet, May 14 2006

Sequence is a permutation of the positive integers and it is its own inverse permutation.
From Antti Karttunen, Nov 05 2016: (Start)
A016945 gives the positions of even terms.
A007310 is closed with respect to this permutation. See A277911 for the permutation induced.
A029744 (without 3) seems to give the positions of records in this sequence (note that it gives the record positions in related A003961 and A048673) which implies that A083658 (without its term 5) would then give the record values.
(End)

Cf. A003961, A064989, A007310, A016945, A029744, A048673, A055396, A083221, A083658, A246277, A246278, A249734, A277911.

A064989 := proc(n) local a,ifs,p ; a := 1 ; ifs := ifactors(n)[2] ; for p in ifs do if op(1,p) > 2 then a := a* prevprime(op(1,p))^op(2,p) ; fi ; od; RETURN(a) ; end: A003961 := proc(n) local a,ifs,p ; a := 1 ; ifs := ifactors(n)[2] ; for p in ifs do a := a* nextprime(op(1,p))^op(2,p) ; od; RETURN(a) ; end: A118306 := proc(nmin) local a,anxt,i,n ; a := [1] ; while nops(a) < nmin do n := nops(a)+1 ; if n in a then anxt := A064989(n) ; else anxt := A003961(n) ; fi ; a := [op(a),anxt] ; od; a ; end: A118306(100) ; # R. J. Mathar, Sep 06 2007

A118306(n) = { if(1==n, 1, my(f = factor(n)); my(d = (-1)^primepi(f[1, 1])); for(i=1, #f~, f[i, 1] = prime(primepi(f[i, 1])-d)); factorback(f)); }; \\ Antti Karttunen, Nov 06 2016
for(n=1, 10001, write("b118306.txt", n, " ", A118306(n)));

(define (A118306 n) (cond ((= 1 n) n) ((odd? (A055396 n)) (A003961 n)) (else (A064989 n)))) ;; Antti Karttunen, Nov 05 2016

From Antti Karttunen, Nov 05 2016: (Start)
a(1) = 1; and for n > 1, if n = a(k) for some k = 1 .. n-1, then a(n) = A064989(n), otherwise a(n) = A003961(n). [After the original definition and R. J. Mathar's Maple-code]
a(1) = 1, and for n > 1, if A055396(n) is odd, a(n) = A003961(n), otherwise a(n) = A064989(n). [The above reduces to this.]
a(n) = product{k>=1} prime(k-((-1)^A055396(n)))^e(k) when n = product{k>=1} prime(k)^e(k).
a(2n) = A249734(n) and a(A249734(n)) = 2n.
A126760(a(A007310(n))) = A277911(n).
For n > 1, A055396(a(n)) = A055396(n) - (-1)^A055396(n). [Permutation sends the terms on any odd row of A246278 to the next even row just below, and vice versa.]
A246277(a(n)) = A246277(n). [While keeping them in the same column.]
a(n) = A064989(A064989(a(A003961(A003961(n))))).
(End)

More terms from R. J. Mathar, Sep 06 2007

A small omission in the definition corrected by Antti Karttunen, Nov 05 2016

cp's OEIS Frontend

A003961 Completely multiplicative with a(prime(k)) = prime(k+1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Perl

Python

Formula

A246278 Prime shift array: Square array read by antidiagonals: A(1,col) = 2*col, and for row > 1, A(row,col) = A003961(A(row-1,col)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

Extensions

A249824 Permutation of natural numbers: a(n) = A078898(A003961(A003961(2*n))).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A249735 Odd bisection of A003961: Replace in 2n-1 each prime factor p(k) with prime p(k+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A118306 If n = product{k>=1} p(k)^b(n,k), where p(k) is the k-th prime and where each b(n,k) is a nonnegative integer, then: If n occurs earlier in the sequence, then a(n) = product{k>=2} p(k-1)^b(n,k); If n does not occur earlier in the sequence, then a(n) = product{k>=1} p(k+1)^b(n,k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Scheme

Formula

Extensions

A249827 Row 3 of A246278: replace in 2n each prime factor p(k) with prime p(k+2).

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula