|
|
A302042
|
|
A032742 analog for a nonstandard factorization process based on the sieve of Eratosthenes (A083221).
|
|
20
|
|
|
1, 1, 1, 2, 1, 3, 1, 4, 3, 5, 1, 6, 1, 7, 5, 8, 1, 9, 1, 10, 9, 11, 1, 12, 5, 13, 7, 14, 1, 15, 1, 16, 15, 17, 7, 18, 1, 19, 11, 20, 1, 21, 1, 22, 21, 23, 1, 24, 7, 25, 25, 26, 1, 27, 25, 28, 27, 29, 1, 30, 1, 31, 13, 32, 11, 33, 1, 34, 33, 35, 1, 36, 1, 37, 17, 38, 11, 39, 1, 40, 39, 41, 1, 42, 35, 43, 35, 44, 1, 45, 49, 46, 45, 47, 13, 48
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Like [A020639(n), A032742(n)] also ordered pair [A020639(n), a(n)] is unique for each n. Iterating n, a(n), a(a(n)), a(a(a(n))), ..., until 1 is reached, and taking the smallest prime factor (A020639) of each term gives a multiset of primes in ascending order, unique for each natural number n >= 1. Permutation pair A250245/A250246 maps between this non-standard prime factorization of n and the ordinary prime factorization of n.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
Collecting the primes given by A020639 we get a multiset of factors: [2, 3, 3, 5]. Note that 2*3*3*5 = 90 = A250246(66).
If we start from n = 66, iterating the map n -> A302044(n) [instead of n -> A302042(n)] and apply A020639 to each term obtained we get just a single instance of each prime: [2, 3, 5]. Then by applying A302045 to the same terms we get the corresponding exponents (multiplicities) of those primes: [1, 2, 1].
|
|
PROG
|
(PARI)
\\ Assuming A250469 and its inverse A268674 have been precomputed, then the following is fast enough:
A302042(n) = if(1==n, n, my(k=0); while((n%2), n = A268674(n); k++); n = n/2; while(k>0, n = A250469(n); k--); (n));
(PARI)
A020639(n) = if(n>1, if(n>n=factor(n, 0)[1, 1], n, factor(n)[1, 1]), 1); \\ From A020639
A078898(n) = if(n<=1, n, my(spf=A020639(n), k=1, m=n/spf); while(m>1, if(A020639(m)>=spf, k++); m--); (k));
\\ Faster if we precompute A078898 as an ordinal transform of A020639:
up_to = 65537;
ordinal_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), pt); for(i=1, length(invec), if(mapisdefined(om, invec[i]), pt = mapget(om, invec[i]), pt = 0); outvec[i] = (1+pt); mapput(om, invec[i], (1+pt))); outvec; };
v078898 = ordinal_transform(vector(up_to, n, A020639(n)));
|
|
CROSSREFS
|
Cf. A020639, A032742, A055396, A078898, A083221, A250245, A250246, A250469, A268674, A276151, A280496, A302032.
Cf. also following analogs: A302041 (omega), A253557 (bigomega), A302043, A302044, A302045 (exponent of the least prime present), A302046 (prime signature filter), A302050 (Moebius mu), A302051 (tau), A302052 (char.fun of squares), A302039, A302055 (Arith. derivative).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|