A032742 -id:A032742 - cp's OEIS frontend

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

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

Offset: 1

Antti Karttunen, Mar 31 2018

nonn

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.

			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.
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].
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].
For n = 5, A020639(5) = 5 and A055396(5) = 3, so a(5) = A250469(A250469(A078898(5))) = A250469(A250469(1)) = 1.
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].

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences generated by sieves

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

\\ 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));

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)));
A078898(n) = v078898[n];
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));

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.
a(n) = A250245(A032742(A250246(n))) = A250245(A280496(n)) = A250245(A250246(n) / A020639(n)).
a(n) = n - A302043(n).

A326062 a(1) = gcd((sigma(n)-A032742(n))-n, n-A032742(n)), where A032742 gives the largest proper divisor of n.

Original entry on oeis.org

1, 1, 2, 1, 4, 3, 6, 1, 1, 1, 10, 2, 12, 1, 2, 1, 16, 3, 18, 2, 2, 1, 22, 12, 1, 1, 2, 14, 28, 3, 30, 1, 2, 1, 2, 1, 36, 1, 2, 10, 40, 3, 42, 2, 6, 1, 46, 4, 1, 1, 2, 2, 52, 3, 2, 4, 2, 1, 58, 6, 60, 1, 2, 1, 2, 3, 66, 2, 2, 1, 70, 3, 72, 1, 2, 2, 2, 3, 78, 2, 1, 1, 82, 14, 2, 1, 2, 4, 88, 9, 2, 2, 2, 1, 2, 12, 96, 1, 6, 1, 100, 3, 102, 2, 2

Offset: 1

Antti Karttunen, Jun 06 2019

nonn

See comments in A326063 and A326064.

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

Cf. A000203, A032742, A060681, A318505, A326061, A326063, A326064.

Cf. also A009194, A325385, A325813, A325975, A326046, A326047, A326048, A326056, A326057, A326060.

A032742(n) = if(1==n,n,n/vecmin(factor(n)[,1]));
A326062(n) = gcd((sigma(n)-A032742(n))-n, n-A032742(n));

a(1) = 1; for n > 1, a(n) = gcd(A060681(n), A318505(n)).

a(n) = gcd((A000203(n)-A032742(n))-n, n-A032742(n)).

A332993 a(1) = 1, for n > 1, a(n) = n + a(A032742(n)).

Original entry on oeis.org

1, 3, 4, 7, 6, 10, 8, 15, 13, 16, 12, 22, 14, 22, 21, 31, 18, 31, 20, 36, 29, 34, 24, 46, 31, 40, 40, 50, 30, 51, 32, 63, 45, 52, 43, 67, 38, 58, 53, 76, 42, 71, 44, 78, 66, 70, 48, 94, 57, 81, 69, 92, 54, 94, 67, 106, 77, 88, 60, 111, 62, 94, 92, 127, 79, 111, 68, 120, 93, 113, 72, 139, 74, 112, 106, 134, 89, 131, 80, 156, 121

Offset: 1

Antti Karttunen, Apr 04 2020

nonn

Sum of those divisors of n that can be obtained by repeatedly taking the largest proper divisor (of previous such divisor, starting from n, which is included in the sum), up to and including the terminal 1.

			a(18) = 18 + 18/2 + 9/3 + 3/3 = 18 + 9 + 3 + 1 = 31.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Cf. A000203, A006022, A032742, A064097, A073934, A332994, A333783, A333791, A333794.

A332993(n) = if(1==n,n,n + A332993(n/vecmin(factor(n)[,1])));

a(1) = 1; and for n > 1, a(n) = n + a(A032742(n)).
a(n) = n + A006022(n).
a(n) = A332994(n) + A333791(n).
a(n) = A000203(n) - A333783(n).
It seems that for all n >= 1, a(n) <= A073934(n) <= A333794(n).

A285729 Compound filter: a(n) = T(A032742(n), A046523(n)), where T(n,k) is sequence A000027 used as a pairing function.

Original entry on oeis.org

1, 2, 2, 12, 2, 31, 2, 59, 18, 50, 2, 142, 2, 73, 50, 261, 2, 199, 2, 220, 73, 131, 2, 607, 33, 166, 129, 314, 2, 961, 2, 1097, 131, 248, 73, 1396, 2, 295, 166, 923, 2, 1246, 2, 550, 340, 401, 2, 2509, 52, 655, 248, 692, 2, 1252, 131, 1303, 295, 590, 2, 3946, 2, 661, 517, 4497, 166, 1924, 2, 1024, 401, 2051, 2, 5707, 2, 898, 655, 1214, 131, 2317, 2, 3781, 888

Offset: 1

Antti Karttunen, May 04 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Pairing Function

Cf. A000027, A032742, A046523, A286142, A286143, A286144, A286149, A286152, A286154, A286160, A286161, A286162, A286163, A286164.

Table[(2 + (#1 + #2)^2 - #1 - 3 #2)/2 & @@ {Sort[Flatten@ Apply[ TensorProduct, # /. {p_, e_} /; p > 1 :> p^Range[0, e]]][[-2]], Times @@ MapIndexed[Prime[First@ #2]^#1 &, Sort[#[[All, -1]], Greater]] - Boole[n == 1]} &@ FactorInteger@ n, {n, 81}] (* Michael De Vlieger, May 04 2017 *)

A032742(n) = if(1==n,n,n/vecmin(factor(n)[,1]));
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ This function from Charles R Greathouse IV, Aug 17 2011
A285729(n) = (1/2)*(2 + ((A032742(n)+A046523(n))^2) - A032742(n) - 3*A046523(n));
for(n=1, 10000, write("b285729.txt", n, " ", A285729(n)));

from sympy import divisors, factorint
def a032742(n): return 1 if n==1 else max(divisors(n)[:-1])
def T(n, m): return ((n + m)**2 - n - 3*m + 2)/2
def P(n):
   f = factorint(n)
   return sorted([f[i] for i in f])
def a046523(n):
    x=1
    while True:
        if P(n) == P(x): return x
        else: x+=1
def a(n): return T(a032742(n), a046523(n)) # Indranil Ghosh, May 05 2017

(define (A285729 n) (* (/ 1 2) (+ (expt (+ (A032742 n) (A046523 n)) 2) (- (A032742 n)) (- (* 3 (A046523 n))) 2)))

a(n) = (1/2)*(2 + ((A032742(n)+A046523(n))^2) - A032742(n) - 3*A046523(n)).

A280497 a(n) = A032742(A249817(n)).

Original entry on oeis.org

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, 13, 17, 7, 18, 1, 19, 21, 20, 1, 21, 1, 22, 11, 23, 1, 24, 7, 25, 25, 26, 1, 27, 13, 28, 33, 29, 1, 30, 1, 31, 19, 32, 19, 33, 1, 34, 37, 35, 1, 36, 1, 37, 17, 38, 11, 39, 1, 40, 15, 41, 1, 42, 31, 43, 45, 44, 1, 45, 17, 46, 57, 47, 37, 48, 1, 49, 27, 50, 1

Offset: 1

Antti Karttunen, Jan 09 2017

nonn

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

Cf. A020639, A032742, A249817.
Differs from related A280496 and A280498 for the first time at n=33, where a(33) = 13, while A280496(33) = A280498(33) = 15.
Differs from related A280495 for the first time at n=42, where a(42) = 21, while A280495(42) = 27.

(define (A280497 n) (A032742 (A249817 n)))

a(n) = A032742(A249817(n)).

a(n) = A249817(n) / A020639(n). [Because A249817 preserves the smallest prime factor of n.]

A280498 a(n) = A032742(A249818(n)).

Original entry on oeis.org

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, 27, 23, 1, 24, 7, 25, 25, 26, 1, 27, 25, 28, 21, 29, 1, 30, 1, 31, 13, 32, 11, 33, 1, 34, 45, 35, 1, 36, 1, 37, 17, 38, 11, 39, 1, 40, 33, 41, 1, 42, 35, 43, 35, 44, 1, 45, 49, 46, 81, 47, 13, 48, 1, 49, 19, 50, 1

Offset: 1

Antti Karttunen, Jan 09 2017

nonn

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

Cf. A020639, A032742, A249818.
Differs from related A280495 and A280497 for the first time at n=33, where a(33) = 15, while A280495(33) = A280497(33) = 13.
Differs from related A280496 for the first time at n=42, where a(42) = 21, while A280496(42) = 27.

(define (A280498 n) (A032742 (A249818 n)))

a(n) = A032742(A249818(n)).

a(n) = A249818(n) / A020639(n). [Because A249818 preserves the smallest prime factor of n.]

A300229 Restricted growth sequence transform of A285729, combining A032742(n) and A046523(n), the largest proper divisor and the prime signature of n.

Original entry on oeis.org

1, 2, 2, 3, 2, 4, 2, 5, 6, 7, 2, 8, 2, 9, 7, 10, 2, 11, 2, 12, 9, 13, 2, 14, 15, 16, 17, 18, 2, 19, 2, 20, 13, 21, 9, 22, 2, 23, 16, 24, 2, 25, 2, 26, 27, 28, 2, 29, 30, 31, 21, 32, 2, 33, 13, 34, 23, 35, 2, 36, 2, 37, 38, 39, 16, 40, 2, 41, 28, 42, 2, 43, 2, 44, 31, 45, 13, 46, 2, 47, 48, 49, 2, 50, 21, 51, 35, 52, 2, 53, 16, 54, 37, 55, 23, 56, 2, 57

Offset: 1

Antti Karttunen, Mar 01 2018

nonn

			a(10) = a(15) (= 7) because both are nonsquare semiprimes (2*5 and 3*5), and when the smallest prime factor is divided out, both yield the same quotient, 5.

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

Cf. A032742, A046523, A285729.

Cf. also A300223, A300226, A300230, A300231, A300232, A300233, A300235.

rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
A032742(n) = if(1==n,n,n/vecmin(factor(n)[,1]));
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ From A046523
A285729(n) = (1/2)*(2 + ((A032742(n)+A046523(n))^2) - A032742(n) - 3*A046523(n));
write_to_bfile(1,rgs_transform(vector(65537,n,A285729(n))),"b300229.txt");

A318505 Sum of divisors of n, up to, but not including the second largest of them A032742(n); a(1) = 0 by convention.

Original entry on oeis.org

0, 0, 0, 1, 0, 3, 0, 3, 1, 3, 0, 10, 0, 3, 4, 7, 0, 12, 0, 12, 4, 3, 0, 24, 1, 3, 4, 14, 0, 27, 0, 15, 4, 3, 6, 37, 0, 3, 4, 30, 0, 33, 0, 18, 18, 3, 0, 52, 1, 18, 4, 20, 0, 39, 6, 36, 4, 3, 0, 78, 0, 3, 20, 31, 6, 45, 0, 24, 4, 39, 0, 87, 0, 3, 24, 26, 8, 51, 0, 66, 13, 3, 0, 98, 6, 3, 4, 48, 0, 99, 8, 30, 4, 3, 6, 108, 0, 24, 24, 67, 0, 63, 0, 54, 52

Offset: 1

Antti Karttunen, Aug 27 2018

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences related to sums of divisors.

Cf. A001065, A013661, A032742, A318504, A318506, A318507, A318508.

A001065(n) = (sigma(n)-n);
A032742(n) = if(1==n,n,n/vecmin(factor(n)[,1]));
A318505(n) = if(1==n,0,A001065(n)-A032742(n));
A318505(n) = sumdiv(n,d,(d<A032742(n))*d); \\ Alternatively.

a(1) = 0; for n > 1, a(n) = A001065(n) - A032742(n).

Sum_{k=1..n} a(k) ~ (zeta(2)/2 - 1/2 - c) * n^2, where c is defined in the corresponding formula in A032742. - Amiram Eldar, Dec 21 2024

A326189 Number of distinct nonnegative integers that are reachable from n with some nonempty combination of transitions x -> A032742(x) and x -> A302042(x).

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 2, 2, 4, 1, 3, 1, 3, 4, 2, 1, 4, 2, 2, 4, 3, 1, 3, 1, 5, 4, 2, 2, 4, 1, 2, 3, 4, 1, 5, 1, 3, 7, 2, 1, 5, 2, 3, 4, 3, 1, 5, 4, 4, 6, 2, 1, 4, 1, 2, 6, 6, 3, 5, 1, 3, 6, 3, 1, 5, 1, 2, 4, 3, 2, 4, 1, 5, 8, 2, 1, 6, 4, 2, 4, 4, 1, 8, 4, 3, 9, 2, 3, 6, 1, 3, 6, 4, 1, 5, 1, 4, 7

Offset: 1

Antti Karttunen, Aug 23 2019

nonn

Number of distinct numbers > 1 in the directed acyclic graph formed by edge relations x -> A032742(x) and x -> A302042(x), where n is the unique root of the graph.

			The directed acyclic graph whose unique root is 153 (illustrated below), spans the following seven numbers [1, 5, 17, 25, 51, 75, 153], as A032742(153) = 51, A302042(153) = 75, A032742(51) = 17, A302042(51) = 25, A032742(75) = 25, A302042(75) = 15, A032742(25) = A302042(25) = 5, and A032742(17) = A302042(17) = A032742(5) = A302042(5) = 1. We exclude the root 153 from the count of numbers that are reached, thus a(153) = 6. (Equally, we can include 153, but exclude 1).
.
        153
       /  \
      /    \
     51    75
     / \  /  \
    /   17    \
    \    |    /
     \   1   /
      \     /
       \   /
        25
         |
         5
         |
         1

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

Cf. A001222, A032742, A253557, A302042, A323888, A326075, A326139, A326190, A326191.

Cf. also A326196.

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; };
A020639(n) = if(n>1, if(n>n=factor(n, 0)[1, 1], n, factor(n)[1, 1]), 1); \\ From A020639
A032742(n) = (n/A020639(n));
v078898 = ordinal_transform(vector(up_to,n,A020639(n)));
A078898(n) = v078898[n];
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));
A326189aux(n,distvals) = if(1==n,distvals,my(newdistvals=setunion([n],distvals),a=A032742(n), b=A302042(n)); newdistvals = A326189aux(a,newdistvals); if(a==b,newdistvals, A326189aux(b,newdistvals)));
A326189(n) = length(A326189aux(n,Set([])));

a(p) = 1 for all primes p.

a(n) >= A326191(n) >= max(A001222(n),A253557(n)) >= min(A001222(n),A253557(n)) >= A326190(n).

A117358 a(n) = A032742(A032742(A032742(n))) = ((n/lpf(n))/lpf(n/lpf(n)))/lpf((n/lpf(n))/lpf(n/lpf(n))), where lpf=A020639, least prime factor.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 3, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 6, 1, 1, 1, 1, 1, 3, 1, 7, 1, 1, 1, 5, 1, 1, 1, 8, 1, 1, 1, 1, 1, 1, 1, 9, 1, 1, 1, 1, 1, 1, 1, 10, 3, 1, 1, 7, 1, 1, 1, 11, 1, 5, 1, 1, 1, 1, 1, 12, 1, 1, 1, 5, 1, 1, 1

Offset: 1

Reinhard Zumkeller, Mar 10 2006

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537
Eric Weisstein's World of Mathematics, Least Prime Factor

Cf. A014673, A032742, A037144, A033987, A054576, A115561.

f[n_] := n/FactorInteger[n][[1, 1]]; (* f is A032742 *)
a[n_] := f@ f@ f@ n;
Array[a, 100] (* Jean-François Alcover, Dec 09 2021 *)
Table[Nest[#/FactorInteger[#][[1,1]]&,n,3],{n,110}] (* Harvey P. Dale, Oct 10 2024 *)

(define (A117358 n) (A032742 (A032742 (A032742 n)))) ;; Antti Karttunen, Dec 07 2017

a(n) = A032742(A032742(A032742(n))) = A032742(A054576(n)) = A054576(n)/A115561(n).

a(A037144(n)) = 1, a(A033987(n)) > 1.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A326062 a(1) = gcd((sigma(n)-A032742(n))-n, n-A032742(n)), where A032742 gives the largest proper divisor of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A332993 a(1) = 1, for n > 1, a(n) = n + a(A032742(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A285729 Compound filter: a(n) = T(A032742(n), A046523(n)), where T(n,k) is sequence A000027 used as a pairing function.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Scheme

Formula

A280497 a(n) = A032742(A249817(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

A280498 a(n) = A032742(A249818(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

A300229 Restricted growth sequence transform of A285729, combining A032742(n) and A046523(n), the largest proper divisor and the prime signature of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A318505 Sum of divisors of n, up to, but not including the second largest of them A032742(n); a(1) = 0 by convention.

Views

Author

Keywords

Links

Crossrefs

Programs