login
A032742 analog for a nonstandard factorization process based on the sieve of Eratosthenes (A083221).
20

%I #30 Apr 05 2018 20:34:17

%S 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,

%T 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,

%U 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

%N A032742 analog for a nonstandard factorization process based on the sieve of Eratosthenes (A083221).

%C 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.

%H Antti Karttunen, <a href="/A302042/b302042.txt">Table of n, a(n) for n = 1..65537</a>

%H <a href="/index/Si#sieve">Index entries for sequences generated by sieves</a>

%F For n > 1, a(n) = A250469^(r)(A078898(n)), where r = A055396(n)-1 and A250469^(r)(n) stands for applying r times the map x -> A250469(x), starting from x = n.

%F a(n) = A250245(A032742(A250246(n))) = A250245(A280496(n)) = A250245(A250246(n) / A020639(n)).

%F a(n) = n - A302043(n).

%e For n = 66, A020639(66) [its smallest prime factor] is 2. Because A055396(66) = A000720(2) = 1, a(66) is just A078898(66) = 66/2 = 33.

%e For n = 33, A020639(33) = 3 and A055396(33) = 2, so a(33) = A250469(A078898(33)) = A250469(6) = 15. [15 is under 6 in array A083221].

%e For n = 15, A020639(15) = 3 and A055396(15) = 2, so a(15) = A250469(A078898(15)) = A250469(3) = 5. [5 is under 3 is array A083221].

%e For n = 5, A020639(5) = 5 and A055396(5) = 3, so a(5) = A250469(A250469(A078898(5))) = A250469(A250469(1)) = 1.

%e 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).

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

%o (PARI)

%o \\ Assuming A250469 and its inverse A268674 have been precomputed, then the following is fast enough:

%o 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));

%o (PARI)

%o A020639(n) = if(n>1, if(n>n=factor(n, 0)[1, 1], n, factor(n)[1, 1]), 1); \\ From A020639

%o 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));

%o \\ Faster if we precompute A078898 as an ordinal transform of A020639:

%o up_to = 65537;

%o 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; };

%o v078898 = ordinal_transform(vector(up_to,n,A020639(n)));

%o A078898(n) = v078898[n];

%o A302042(n) = if((1==n)||isprime(n),1,my(c = A078898(n), p = prime(-1+primepi(A020639(n))+primepi(A020639(c))), d = A078898(c), k=0); while(d, k++; if((1==k)||(A020639(k)>=p),d -= 1)); (k*p));

%Y Cf. A020639, A032742, A055396, A078898, A083221, A250245, A250246, A250469, A268674, A276151, A280496, A302032.

%Y 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).

%K nonn

%O 1,4

%A _Antti Karttunen_, Mar 31 2018