Displaying 1-10 of 16 results found.
1, 2, 3, 4, 5, 8, 7, 6, 9, 14, 11, 24, 13, 26, 15, 10, 17, 20, 19, 34, 21, 44, 23, 48, 25, 32, 27, 124, 29, 80, 31, 12, 33, 74, 35, 54, 37, 62, 39, 76, 41, 38, 43, 174, 45, 134, 47, 120, 49, 50, 51, 64, 53, 98, 55, 342, 57, 104, 59, 624, 61, 242, 63, 16, 65, 56, 67, 244, 69, 224, 71, 90, 73, 68
COMMENTS
To compute a(n) we shift its binary representation right as many steps k as necessary that the result were an odd number. Then one is added to that odd number, and the prime factorization of the resulting even number is shifted the same k number of steps towards larger primes, whose product is then decremented by one to get the final result.
In the essence, a(n) tells which number in array A246275 is at the same position where n is in the array A135764. As the topmost row in both arrays is A005408 (odd numbers), they are fixed, i.e. a(2n+1) = 2n+1 for all n. Equally: a(n) tells which number in array A246273 is at the same position where n is in the array A054582, as they are the transposes of above two arrays.
FORMULA
a(n) = A242378( A007814(n), (1+ A000265(n))) - 1. [Where the bivariate function A242378(k,n) changes each prime p(i) in the prime factorization of n to p(i+k), i.e., it's the result of A003961 iterated k times starting from n]. As a composition of related permutations:
Other identities:
EXAMPLE
Consider n=36, "100100" in binary. It has to be shifted two bits right that the result were an odd number 9, "1001" in binary. We see that 9+1 = 10 = 2*5 = p_1 * p_3 [where p_k denotes the k-th prime, A000040(k)], and shifting this two steps towards larger primes results p_3 * p_5 = 5*11 = 55, thus a(36) = 55-1 = 54.
PROG
(PARI)
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
A246676(n) = { my(k=0); while(!(n%2), n = n\2; k++); n++; while(k>0, n = A003961(n); k--); n-1; };
for(n=1, 8192, write("b246676.txt", n, " ", A246676(n)));
1, 2, 3, 4, 5, 8, 7, 6, 9, 14, 15, 24, 13, 26, 11, 10, 17, 20, 27, 34, 29, 80, 47, 48, 25, 32, 51, 124, 21, 44, 19, 12, 33, 74, 39, 54, 53, 98, 67, 76, 57, 104, 159, 624, 93, 404, 95, 120, 49, 50, 63, 64, 101, 152, 247, 342, 41, 38, 87, 174, 37, 62, 23, 16, 65, 56, 147, 244, 77, 188, 107, 90, 105, 374, 195, 324, 133, 170, 151, 142, 113, 92
COMMENTS
See the comments in A246676. This is otherwise similar permutation, except that after having reached an odd number 2m-1 when we have shifted the binary representation of n right k steps, here, in contrary to A246676, we don't shift the primes in the prime factorization of the even number 2m, but instead of an even number (2*a(m)), shifting it the same number (k) of positions towards larger primes, whose product is then decremented by one to get the final result. This can be viewed as an entanglement or encoding permutation where the complementary pairs of sequences to be interwoven together are even and odd numbers ( A005843/ A005408) which are entangled with another complementary pair: even numbers in the order they appear in A253885 and odd numbers in their usual order: ( A253885/ A005408). From the above follows also that this sequence can be represented as a binary tree. Each child to the left is obtained by doubling the parent and subtracting one, and each child to the right is obtained by applying A253885 to the parent: 1
|
...................2...................
3 4
5......../ \........8 7......../ \........6
/ \ / \ / \ / \
/ \ / \ / \ / \
/ \ / \ / \ / \
9 14 15 24 13 26 11 10
17 20 27 34 29 80 47 48 25 32 51 124 21 44 19 12
(End)
FORMULA
a(1) = 1, a(n) = A242378( A007814(n), 2*a( A003602(n))) - 1. [Where the bivariate function A242378(k,n) changes each prime p(i) in the prime factorization of n to p(i+k), i.e., it's the result of A003961 iterated k times starting from n]. As a composition of other permutations:
Other identities. For all n >= 1, the following holds:
a(n) = (1+a((2*n)-1))/2. [The odd bisection from a(1) onward with one added and then halved gives the sequence back].
For all n >= 0, the following holds: a( A000051(n)) = A000051(n). [Numbers of the form 2^n + 1 are among the fixed points].
EXAMPLE
Consider n=30, "11110" in binary. It has to be shifted just one bit-position right that the result were an odd number 15, "1111" in binary. As 15 = 2*8-1, we use 2*a(8) = 2*6 = 12 = 2*2*3 = p_1 * p_1 * p_2 [where p_k denotes the k-th prime, A000040(k)], which we shift one step towards larger primes resulting p_2 * p_2 * p_3 = 3*3*5 = 45, thus a(30) = 45-1 = 44.
PROG
(PARI)
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
A246684(n) = { my(k=0); if(1==n, 1, while(!(n%2), n = n/2; k++); n = 2* A246684((n+1)/2); while(k>0, n = A003961(n); k--); n-1); };
for(n=1, 8192, write("b246684.txt", n, " ", A246684(n))); (Scheme, with memoization-macro definec, two implementations)
CROSSREFS
Differs from A249814 for the first time at n=14, where a(14) = 26, while A249814(14) = 20.
a(0) = 2, for n > 0, a(n) = a(n-1)* A242378(n,a(n-1)), where A242378(n,a(n-1)) shifts the prime factorization of a(n-1) n primes towards larger primes with A003961.
+20
7
2, 6, 210, 3573570, 64845819350301990, 28695662573739152697846686144187168109530, 1038300112150956151877699324649731518883355380534272386781875587619359740733888844803014212990
FORMULA
a(0) = 2, for n > 0, a(n) = a(n-1)* A242378(n,a(n-1)). Other identities. For all n >= 0:
PROG
(PARI)
A003961(n) = { my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); };
(Python)
from sympy import factorint, prime, primepi
from operator import mul
from functools import reduce
def a003961(n):
f=factorint(n)
return 1 if n==1 else reduce(mul, [prime(primepi(i) + 1)**f[i] for i in f])
def a242378(k, n):
while k>0:
n=a003961(n)
k-=1
return n
l=[2]
for n in range(1, 7):
x=l[n - 1]
l.append(x*a242378(n, x))
Permutation of natural numbers: a(1) = 1, a(2n+1) = 1 + 2*a(n), a(2n) = A242378( A001511(n), (1+ A000265(n))) - 1.
+20
6
1, 2, 3, 4, 5, 8, 7, 6, 9, 14, 11, 24, 17, 26, 15, 10, 13, 20, 19, 34, 29, 44, 23, 48, 49, 32, 35, 124, 53, 80, 31, 12, 21, 74, 27, 54, 41, 62, 39, 76, 69, 38, 59, 174, 89, 134, 47, 120, 97, 50, 99, 64, 65, 98, 71, 342, 249, 104, 107, 624, 161, 242, 63, 16, 25, 56, 43, 244, 149, 224, 55, 90, 109, 68, 83
COMMENTS
See the comments in A246676. This is a similar permutation, except for odd numbers, which are here recursively permuted by the emerging permutation itself. The even bisection halved gives A246680, the odd bisection from a(3) onward with one subtracted and then halved gives this sequence back.
FORMULA
a(1) = 1, a(2n+1) = 1 + 2*a(n), a(2n) = A242378( A001511(n), (1+ A000265(n))) - 1. [Where the bivariate function A242378(k,n) changes each prime p(i) in the prime factorization of n to p(i+k), i.e., it's the result of A003961 iterated k times starting from n].
PROG
(Scheme, with memoization-macro definec)
(definec ( A246678 n) (cond ((<= n 1) n) ((odd? n) (+ 1 (* 2 ( A246678 (/ (- n 1) 2))))) (else (+ -1 (A242378bi ( A007814 n) (+ 1 ( A000265 n))))))) ;; Code for A242378bi given in A242378.
0, 0, 1, 0, 1, 2, 0, 1, 3, 3, 0, 1, 5, 5, 4, 0, 1, 7, 7, 9, 5, 0, 1, 11, 11, 25, 7, 6, 0, 1, 13, 13, 49, 11, 15, 7, 0, 1, 17, 17, 121, 13, 35, 11, 8, 0, 1, 19, 19, 169, 17, 77, 13, 27, 9, 0, 1, 23, 23, 289, 19, 143, 17, 125, 25, 10, 0, 1, 29, 29, 361, 23, 221, 19, 343, 49, 21, 11
Completely multiplicative with a(prime(k)) = prime(k+1).
+10
873
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
COMMENTS
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 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)
REFERENCES
Richard K. Guy, editor, Problems From Western Number Theory Conferences, Labor Day, 1983, Problem 367 (Proposed by Leroy F. Meyers, The Ohio State U.).
FORMULA
If n = Product p(k)^e(k) then a(n) = Product p(k+1)^e(k).
(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
EXAMPLE
a(12) = a(2^2 * 3) = a(prime(1)^2 * prime(2)) = prime(2)^2 * prime(3) = 3^2 * 5 = 45.
MAPLE
a:= n-> mul(nextprime(i[1])^i[2], i=ifactors(n)[2]):
MATHEMATICA
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 *)
PROG
(PARI) 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]))
(PARI) 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 (Haskell)
a003961 1 = 1
a003961 n = product $ map (a000040 . (+ 1) . a049084) $ a027746_row n
(MIT/GNU Scheme, with Aubrey Jaffer's SLIB Scheme library)
(require 'factor)
(Perl) use ntheory ":all"; sub a003961 { vecprod(map { next_prime($_) } factor(shift)); } # Dana Jacobsen, Mar 06 2016 (Python)
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)
CROSSREFS
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. 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. Applying the same transformation again gives A357852.
Self-inverse permutation of the positive integers induced by partition enumeration in A112798 and partition conjugation.
+10
291
1, 2, 4, 3, 8, 6, 16, 5, 9, 12, 32, 10, 64, 24, 18, 7, 128, 15, 256, 20, 36, 48, 512, 14, 27, 96, 25, 40, 1024, 30, 2048, 11, 72, 192, 54, 21, 4096, 384, 144, 28, 8192, 60, 16384, 80, 50, 768, 32768, 22, 81, 45, 288, 160, 65536, 35, 108, 56, 576, 1536, 131072, 42
COMMENTS
Factor n; replace each prime(i) with i, take the conjugate partition, replace parts i with prime(i) and multiply out.
Because the partition conjugation doesn't change the partition's total sum, this permutation preserves A056239, i.e., A056239(a(n)) = A056239(n) for all n. (Similarly, for all n, A001221(a(n)) = A001221(n), because the number of steps in the Ferrers/Young-diagram stays invariant under the conjugation. - Note added Apr 29 2022). Because this permutation commutes with A241909, in other words, as a( A241909(n)) = A241909(a(n)) for all n, from which follows, because both permutations are self-inverse, that a(n) = A241909(a( A241909(n))), it means that this is also induced when partitions are conjugated in the partition enumeration system A241918. (Not only in A112798.) (End)
Rows in arrays A243060 and A243070 converge towards this sequence, and also, assuming no surprises at the rate of that convergence, this sequence occurs also as the central diagonal of both. Each even number is mapped to a unique term of A102750 and vice versa. Conversely, each odd number (larger than 1) is mapped to a unique term of A070003, and vice versa. The permutation pair A243287- A243288 has the same property. This is also used to induce the permutations A244981- A244984. Taking the odd bisection and dividing out the largest prime factor results in the permutation A243505. Conversely, with A245614 (the inverse of above), shares the property that each term of A244990 is mapped to a unique term of A028260 and each term of A244991 is mapped to a unique term of A026424. (End)
The Maple program follows the steps described in the first comment. The subprogram C yields the conjugate partition of a given partition. - Emeric Deutsch, May 09 2015 The Heinz number of the partition that is conjugate to the partition with Heinz number n. The Heinz number of a partition p = [p_1, p_2, ..., p_r] is defined as Product(p_j-th prime, j=1...r). Example: a(3) = 4. Indeed, the partition with Heinz number 3 is [2]; its conjugate is [1,1] having Heinz number 4. - Emeric Deutsch, May 19 2015
FORMULA
a(1) = 1, a(p_i) = 2^i, and for other cases, if n = p_i1 * p_i2 * p_i3 * ... * p_{k-1} * p_k, where p's are primes, not necessarily distinct, sorted into nondescending order so that i1 <= i2 <= i3 <= ... <= i_{k-1} <= ik, then a(n) = 2^(ik-i_{k-1}) * 3^(i_{k-1}-i_{k-2}) * ... * p_{i_{k-1}}^(i2-i1) * p_ik^(i1).
This can be implemented as a recurrence, with base case a(1) = 1,
and then using any of the following three alternative formulas:
a(n) = ( A000040( A071178(n))^ A241919(n)) * A242378( A071178(n), a( A051119(n))). [Here ^ stands for the ordinary exponentiation, and the bivariate function A242378(k,n) changes each prime p(i) in the prime factorization of n to p(i+k), i.e., it's the result of A003961 iterated k times starting from n.] (End)
As a composition of related permutations:
Other identities. For all n >= 1, the following holds:
A006530(a(n)) = A105560(n). [The latter sequence gives greatest prime factor of the n-th term].
A243503(a(n)) = A243503(n). [Because partition conjugation does not change the partition size.]
(End)
MAPLE
with(numtheory): c := proc (n) local B, C: B := proc (n) local pf: pf := op(2, ifactors(n)): [seq(seq(pi(op(1, op(i, pf))), j = 1 .. op(2, op(i, pf))), i = 1 .. nops(pf))] end proc: C := proc (P) local a: a := proc (j) local c, i: c := 0; for i to nops(P) do if j <= P[i] then c := c+1 else end if end do: c end proc: [seq(a(k), k = 1 .. max(P))] end proc: mul(ithprime(C(B(n))[q]), q = 1 .. nops(C(B(n)))) end proc: seq(c(n), n = 1 .. 59); # Emeric Deutsch, May 09 2015 # second Maple program:
a:= n-> (l-> mul(ithprime(add(`if`(j<i, 0, 1), j=l)), i=1..max(l)))(
[seq(numtheory[pi](i[1])$i[2], i=ifactors(n)[2])]):
MATHEMATICA
A122111[1] = 1; A122111[n_] := Module[{l = #, m = 0}, Times @@ Power @@@ Table[l -= m; l = DeleteCases[l, 0]; {Prime@Length@l, m = Min@l}, Length@Union@l]] &@Catenate[ConstantArray[PrimePi[#1], #2] & @@@ FactorInteger@n]; Array[ A122111, 60] (* JungHwan Min, Aug 22 2016 *)
a[n_] := Function[l, Product[Prime[Sum[If[j<i, 0, 1], {j, l}]], {i, 1, Max[l]}]][Flatten[Table[Table[PrimePi[f[[1]]], {f[[2]]}], {f, FactorInteger[n]}]]];
PROG
(PARI) A122111(n) = if(1==n, n, my(f=factor(n), es=Vecrev(f[, 2]), is=concat(apply(primepi, Vecrev(f[, 1])), [0]), pri=0, m=1); for(i=1, #es, pri += es[i]; m *= prime(pri)^(is[i]-is[1+i])); (m)); \\ Antti Karttunen, Jul 20 2020 (Scheme)
(Scheme)
(Scheme)
(Python)
from sympy import factorint, prevprime, prime, primefactors
from operator import mul
def a001222(n): return 0 if n==1 else a001222(n/primefactors(n)[0]) + 1
def a064989(n):
f=factorint(n)
return 1 if n==1 else reduce(mul, [1 if i==2 else prevprime(i)**f[i] for i in f])
def a105560(n): return 1 if n==1 else prime(a001222(n))
def a(n): return 1 if n==1 else a105560(n)*a(a064989(n))
CROSSREFS
Cf. A112798, A241918 (conjugates the partitions listed in these two tables). Cf. A243060 and A243070. (Limit of rows in these arrays, and also their central diagonal). Cf. also A080576, A036036, A001221, A001222, A061395, A243503, A056239, A052126, A003961, A064989, A071178, A241917, A241919, A242378, A242424, A006530, A105560, A070003, A102750, A066829, A028260, A026424, A244990, A244991, A244992, A108951, A181815, A181819, A181820, A238745, A238690, A242421. Cf. A319988 (parity of this sequence for n > 1), A336124 (a(n) mod 4). Other related permutations: A048673- A064216, A244981- A244982, A244983- A244984, A243287- A243288, A243505- A243506, A245613- A245614, A075157, A075158, A129594, A069799, A242415, A245451, A245452, A245454, also A336321 & A336322 (composed with A225546). Cf. also array A350066 [A(i, j) = a(a(i)*a(j))].
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)).
+10
83
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
COMMENTS
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. 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)
FORMULA
A(1,col) = 2*col, and for row > 1, A(row,col) = A003961(A(row-1,col)). As a composition of other similar sequences:
EXAMPLE
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, ...
MATHEMATICA
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 *)
PROG
(Scheme)
(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))))
CROSSREFS
First row: A005843 (the even numbers), from 2 onward. Column 1: A000040 (primes), Column 2: A001248 (squares of primes), Column 3: A006094 (products of two successive primes), Column 4: A030078 (cubes of primes). 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).
EXTENSIONS
Starting offset of the linear sequence changed from 1 to 2, without affecting the column and row indices by Antti Karttunen, Jan 03 2015
Self-inverse permutation of natural numbers: a(1)=1, a(p_i) = 2^i, and if n = p_i1 * p_i2 * p_i3 * ... * p_{ik-1} * p_ik, where p's are primes, with their indexes are sorted into nondescending order: i1 <= i2 <= i3 <= ... <= i_{k-1} <= ik, then a(n) = 2^(i1-1) * 3^(i2-i1) * 5^(i3-i2) * ... * p_k^(1+(ik-i_{k-1})). Here k = A001222(n) and ik = A061395(n).
+10
54
1, 2, 4, 3, 8, 9, 16, 5, 6, 27, 32, 25, 64, 81, 18, 7, 128, 15, 256, 125, 54, 243, 512, 49, 12, 729, 10, 625, 1024, 75, 2048, 11, 162, 2187, 36, 35, 4096, 6561, 486, 343, 8192, 375, 16384, 3125, 50, 19683, 32768, 121, 24, 45, 1458, 15625, 65536, 21, 108, 2401
COMMENTS
This permutation maps between the partitions as ordered in A112798 and A241918 (the original motivation for this sequence). For all n > 2, A007814(a(n)) = A055396(n)-1, which implies that this self-inverse permutation maps between primes ( A000040) and the powers of two larger than one ( A000079(n>=1)), and apart from a(1) & a(2), this also maps each even number to some odd number, and vice versa, which means there are no fixed points after 2.
FORMULA
If n is a prime with index i (p_i), then a(n) = 2^i, otherwise when n = p_i1 * p_i2 * p_i3 * ... p_ik, where p_i1, p_i2, p_i3, ..., p_ik are the primes present (not necessarily all distinct) in the prime factorization of n, sorted into nondescending order, a(n) = 2^(i1-1) * 3^(i2-i1) * 5^(i3-i2) * ... * p_k^(1+(ik-i_{k-1})).
Equally, if n = 2^k, then a(n) = p_k, otherwise, when n = 2^e1 * 3^e2 * 5^e3 * ... * p_k^{e_k}, i.e., where e1 ... e_k are the exponents (some of them possibly zero, except the last) of the primes 2, 3, 5, ... in the prime factorization of n, a(n) = p_{1+e1} * p_{1+e1+e2} * p_{1+e1+e2+e3} * ... * p_{e1+e2+e3+...+e_k}.
From the equivalence of the above two formulas (which are inverses of each other) it follows that a(a(n)) = n, i.e., that this permutation is an involution. For a proof, please see the attached notes.
The first formula corresponds to this recurrence:
And the latter formula with this recurrence:
[Here A242378(k,n) changes each prime p(i) in the prime factorization of n to p(i+k), i.e., it's the result of A003961 iterated k times starting from n.] We also have:
For all n > 1, a(2n-1) = 2*a( A064216(n)).
EXAMPLE
For n = 12 = 2 * 2 * 3 = p_1 * p_1 * p_2, we obtain by the first formula 2^(1-1) * 3^(1-1) * 5^(1+(2-1)) = 5^2 = 25. By the second formula, as n = 2^2 * 3^1, we obtain the same result, p_{1+2} * p_{2+1} = p_3 * p_3 = 25, thus a(12) = 25.
Using the product formula over the terms of row n of table A241918, we see, because 9450 = 2*3*3*3*5*5*7 = p_1^1 * p_2^3 * p_3^2 * p_4^1, that the corresponding row in A241918 is {2,5,7,7}, and multiplying p_2 * p_5 * p_7^2 yields 3 * 11 * 17 * 17 = 9537, thus a(9450) = 9537. Similarly, for 9537, the corresponding row in A241918 is {1,2,2,2,3,3,4}, and multiplying p_1^1 * p_2^3 * p_3^2 * p_4^1, we obtain 9450 back.
MATHEMATICA
Array[If[# == 1, 1, Function[t, Times @@ Prime@ Accumulate[If[Length@ t < 2, {0}, Join[{1}, ConstantArray[0, Length@ t - 2], {-1}]] + ReplacePart[t, Map[#1 -> #2 & @@ # &, #]]]]@ ConstantArray[0, Transpose[#][[1, -1]]] &[FactorInteger[#] /. {p_, e_} /; p > 0 :> {PrimePi@ p, e}]] &, 56] (* Michael De Vlieger, Jan 23 2020 *)
PROG
;; Another recursive version:
(define (pow2? n) (let loop ((n n) (i 0)) (cond ((zero? n) #f) ((odd? n) (and (= 1 n) i)) (else (loop (/ n 2) (1+ i)))))) ;; Gives non-false only when n is a power of two.
(Haskell)
a241909 1 = 1
a241909 n = product $ zipWith (^) a000040_list $ zipWith (-) is (1 : is)
where is = reverse ((j + 1) : js)
(j:js) = reverse $ map a049084 $ a027746_row n
(PARI) A241909(n) = if(1==n||isprime(n), 2^primepi(n), my(f=factor(n), h=1, i, m=1, p=1, k=1); while(k<=#f~, p = nextprime(1+p); i = primepi(f[k, 1]); m *= p^(i-h); h = i; if(f[k, 2]>1, f[k, 2]--, k++)); (p*m)); \\ Antti Karttunen, Jan 17 2020
CROSSREFS
Cf. A203623, A241918, A242378, A007814, A064989, A064216, A001222, A061395, A125976, A243060, A243070.
Square array A(n,k) = prime(n+1)^(2^k), read by descending antidiagonals (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ...; Fermi-Dirac primes ( A050376) in matrix form, sorted into rows by their prime divisor.
+10
19
2, 4, 3, 16, 9, 5, 256, 81, 25, 7, 65536, 6561, 625, 49, 11, 4294967296, 43046721, 390625, 2401, 121, 13, 18446744073709551616, 1853020188851841, 152587890625, 5764801, 14641, 169, 17, 340282366920938463463374607431768211456, 3433683820292512484657849089281, 23283064365386962890625, 33232930569601, 214358881, 28561, 289, 19
COMMENTS
This sequence is a permutation of A050376, so every positive integer is the product of a unique subset, S_factors, of its terms. If we restrict S_factors to be chosen from a subset, S_0, consisting of numbers from specified rows and/or columns of this array, there are notable sequences among those that may be generated. See the examples. Other notable sequences can be generated if we restrict the intersection of S_factors with specific rows/columns to have even cardinality. In any of the foregoing cases, the numbers in the resulting sequence form a group under the binary operation A059897(.,.). Shares with array A246278 the property that columns grow downward by iterating A003961, and indeed, this array can be obtained from A246278 by selecting its columns 1, 2, 8, 128, ..., 2^((2^k)-1), for k >= 0. A(n,k) is the image of the lattice point with coordinates X=n and Y=k under the inverse of the bijection f defined in the first comment of A306697. This geometric relationship can be used to construct an isomorphism from the polynomial ring GF(2)[x,y] to a ring over the positive integers, using methods similar to those for constructing A297845 and A306697. See A329329, the ring's multiplicative operator, for details.
FORMULA
A(0,k) = 2^(2^k), and for n > 0, A(n,k) = A003961(A(n-1,k)). A(n,k+1) = A000290(A(n,k)) = A(n,k)^2.
EXAMPLE
The top left 5 X 5 corner of the array:
n\k | 0 1 2 3 4
----+-------------------------------------------------------
0 | 2, 4, 16, 256, 65536, ...
1 | 3, 9, 81, 6561, 43046721, ...
2 | 5, 25, 625, 390625, 152587890625, ...
3 | 7, 49, 2401, 5764801, 33232930569601, ...
4 | 11, 121, 14641, 214358881, 45949729863572161, ...
Column 0 continues as a list of primes, column 1 as a list of their squares, column 2 as a list of their 4th powers, and so on.
Every nonnegative power of 2 ( A000079) is a product of a unique subset of numbers from row 0; every squarefree number ( A005117) is a product of a unique subset of numbers from column 0. Likewise other rows and columns generate the sets of numbers from sequences: Column 1: A062503 Squares of squarefree numbers. Column 2: A113849 4th powers of squarefree numbers. Union of rows 0 and 1: A003586 3-smooth numbers. Union of columns 0 and 1: A046100 Biquadratefree numbers. Union of row 0 / column 0: A122132 Oddly squarefree numbers. Row 0 excluding column 0: A000302 Powers of 4. Column 0 excluding row 0: A056911 Squarefree odd numbers. All rows except 0: A005408 Odd numbers. All columns except 0: A000290\{0} Positive squares. All rows except 1: A001651 Numbers not divisible by 3. All columns except 1: A252895 (have odd number of square divisors). If, instead of restrictions on choosing individual factors of the product, we restrict the product to be of an even number of terms from each row of the array, we get A262675. The equivalent restriction applied to columns gives us A268390; applied only to column 0, we get A028260 (product of an even number of primes).
MATHEMATICA
Table[Prime[#]^(2^k) &[m - k + 1], {m, 0, 7}, {k, m, 0, -1}] // Flatten (* Michael De Vlieger, Dec 28 2019 *)
PROG
(PARI)
up_to = 105;
A329050sq(n, k) = (prime(1+n)^(2^k));
A329050list(up_to) = { my(v = vector(up_to), i=0); for(a=0, oo, for(col=0, a, i++; if(i > up_to, return(v)); v[i] = A329050sq(col, a-col))); (v); };
v329050 = A329050list(up_to);
CROSSREFS
See also the table in the example section.
EXTENSIONS
Example annotated for clarity by Peter Munn, Feb 12 2020
Search completed in 0.019 seconds
|