A037916 -id:A037916 - cp's OEIS frontend

A342679 Number of steps for n to reach 1 or n by repeated application of A037916, or -1 if they are never reached.

1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 2, 3, 1, 4, 1, 3, 2, 2, 1, 2, 2, 2, 2, 3, 1, 3, 1, 2, 2, 2, 2, 3, 1, 2, 2, 2, 1, 3, 1, 3, 3, 2, 1, 2, 2, 4, 2, 3, 1, 2, 2, 2, 2, 2, 1, 2, 1, 2, 3, 3, 2, 3, 1, 3, 2, 3, 1, 3, 1, 2, 4, 3, 2, 3, 1, 2, 3, 2, 1, 2, 2, 2, 2, 2, 1

Offset: 2

Devansh Singh, Mar 18 2021

Let n = (p1^a1)*(p2^a2)*...*(pk^aj) be the prime-factorization of n >= 2, where primes are in ascending order and ai >= 1 for all i >= 1 and <= k, then form n' = a1 a2 a3 ... ak = A037916(n), the concatenation of the exponents. Repeat this process if n' != 1 and != n, otherwise stop.
When n is prime, a(n) = 1; when n is semiprime, a(n) = 2.
Does every n reach 1 by this process, or does there exist some n whose trajectory enters a cycle, i.e., we reach n again instead of 1?
No cycles for n <= 10^9. - Michael S. Branicky, Mar 21 2021

			3 = 3^1 -> 1, so a(3) = 1;
6 = 2^1 * 3^1 -> 11 = 11^1 -> 1, so a(6) = 2;
16 = 2^4 -> 4 = 2^2 -> 2 = 2^1 -> 1, so a(16) = 3;
50 = 2^1 * 5^2 -> 12 = 2^2 * 3^1 -> 21 = 3^1 * 7^1 -> 11 -> 1, so a(50) = 4.

Cf. A000040, A037916.

Table[Length@Rest@Most@FixedPointList[FromDigits[Last/@FactorInteger@#]&,k],{k,2,100}] (* Giorgos Kalogeropoulos, Apr 01 2021 *)

f(n) = my(f=factor(n)[,2], s=""); for(i=1, #f~, s=concat(s,Str(f[i]))); eval(s); \\ A037916
a(n) = my(k=n, nb=0); while (k != 1, k = f(k); nb++); nb; \\ Michel Marcus, Mar 18 2021

import sympy
N=int(input())
A342679_n=[]
for n in range(2,N+1):
    n_0=n
    steps=0
    while not sympy.isprime(n) :
        exponents=list(sympy.factorint(n).values())
        m=""
        for i in exponents:
            m=m+str(i)
        n=int(m)
        if n==n_0:
            break
        steps+=1
    A342679_n.append(steps+1)
print(A342679_n)

def a(n):
  c, iter = 1, A037916(n)
  while iter != 1 and iter != n: c, iter = c+1, A037916(iter)
  return c
print([a(n) for n in range(2, 89)]) # Michael S. Branicky, Mar 20 2021

A077462 Prime factor configuration patterns.

Original entry on oeis.org

0, 1, 2, 2, 3, 2, 4, 2, 5, 3, 4, 2, 6, 2, 4, 4, 7, 2, 8, 2, 6, 4, 4, 2, 9, 3, 4, 5, 6, 2, 10, 2, 11, 4, 4, 4, 12, 2, 4, 4, 9, 2, 10, 2, 6, 6, 4, 2, 13, 3, 8, 4, 6, 2, 14, 4, 9, 4, 4, 2, 15, 2, 4, 6, 16, 4, 10, 2, 6, 4, 10, 2, 17, 2, 4, 8, 6, 4, 10, 2, 13, 7, 4

Offset: 0

Michael Somos, Nov 07 2002

Call two numbers equivalent if they have the same prime factorization exponents (in the same order). This sequence enumerates the equivalence classes.
A055932(a(n)) = A071364(n). - David Wasserman, Dec 21 2004
From Antti Karttunen, Jun 13 2018: (Start)
After a(0) = 0, this is the restricted growth sequence transform of A071364. The latter sequence is an "ordered variant" of A046523, and because A101296 is the rgs-transform of A046523, it follows that for all i, j: a(i) = a(j) => A101296(i) = A101296(j).
(End)

			12 = 2^2*3^1 has exponents {2,1}, and is the first number with that pattern, so its value is one more than the largest previous value; a(12) = 6. Contrast that with 18 = 2^1*3^2 having exponents {1,2}, which is different from {2,1}, so a(18) is not equal to a(12). - _Franklin T. Adams-Watters_, Aug 01 2012

Antti Karttunen, Table of n, a(n) for n = 0..100000 (terms 0..10000 from T. D. Noe)
S. Whealton, Prime Factor Configuration Pattern Numbers.

Cf. A037916, A071364, A101296, A290110, A300250.

One more than A079616.

fList = {{0}}; Join[{0, 1}, Table[e = Transpose[FactorInteger[n]][[2]]; pos = Position[fList, e]; If[pos == {}, AppendTo[fList, e]; Length[fList], pos[[1, 1]]], {n, 2, 100}]] (* T. D. Noe, Aug 01 2012 *)

a(n)=local(vn); if(n<1,return(0)); vn=factor(n)[,2]; for(i=1,n,if(vn==factor(i)[,2],return(#Set(vector(i,j,factor(j)[,2])))))

up_to = 100000;
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; };
A071364(n) = { my(f = factor(n)); for (i=1, #f~, f[i, 1] = prime(i)); factorback(f); }; \\ From A071364
v077462 = rgs_transform(vector(up_to,n,A071364(n)));
A077462(n) = if(!n,n,v077462[n]); \\ Antti Karttunen, Jun 13 2018

A282231 First term of A175304 with a given prime signature.

Original entry on oeis.org

3, 6, 12, 60, 70, 72, 96, 125, 128, 250, 264, 450, 480, 756, 1152, 1380, 1458, 1980, 2030, 2048, 3640, 4860, 6552, 7776, 10648, 11448, 11907, 12348, 14960, 17664, 18432, 27540, 31620, 34200, 40500, 42978, 58140, 65000, 75776, 102240, 131328, 146529, 153120

Offset: 1

Vladimir Shevelev, Feb 09 2017

nonn

Conjecturally the sequence is infinite.
The sequence of the corresponding prime signatures begins  p, p*q, p^2*q, p^2*q*r, p*q*r, p^3*q^2, p^5*q, p^3, p^7, ...
There are no prime signatures of perfect squares. Indeed, A175304 contains no squares (see our comment there). - Vladimir Shevelev, Feb 10 2017
A037916(a(n)) gives a numerical version of the second comment: {1,11,21,211,111,32,51,3,7,31,311,221,511,321,72,2111,61,2211,1111,...}, however due to the limitations of the notation in A037916, we cannot represent a(20)=2048 since A037916(2^10)=digit 10, which is not a valid decimal digit. A037916 is useful if we refrain from rendering the multiplicities as decimal digits, instead maintaining them as a list. - Michael De Vlieger, Feb 10 2017

			From _Michael De Vlieger_, Feb 10 2017: (Start)
a(1) = 3 since 3 is prime and has a prime signature of "1"; it is the very first prime in the sequence, followed by {5,11,17,29,41,...}. The prime signature "1" is the first distinct signature encountered in the sequence
a(2) = 6 since it is a squarefree semiprime with prime signature "11"; it is the very first such number in the sequence, followed by {10,22,34, 35,51,...}. This prime signature is the second distinct signature encountered in the sequence.
a(3) = 12 since it has a prime signature of "21" (i.e., the exponents of  p^2*q^1, A037916(12)=21) and this signature is the third distinct signature encountered. It is the very first number with this signature, followed by {44,92,147,236,332,...}. (End)

Charles R Greathouse IV, Table of n, a(n) for n = 1..234

Cf. A025487, A037916, A175304, A282175.

Map[#[[1, 1]] &, GatherBy[#, Last]] &@ Map[{#, Reverse@ Sort@ FactorInteger[#][[All, -1]]} &, Select[Range[10^6], Function[n, DivisorSigma[0, n + #] == # &@ DivisorSigma[0, n]]]] (* Michael De Vlieger, Feb 10 2017 *)

sig(n)=vecsort(factor(n)[,2]~,,4)
has(n)=my(d=numdiv(n)); d==numdiv(n+d)
try(n)=my(t); has(n) && !mapisdefined(m,t=sig(n)) && (mapput(m,t,0) || 1)
v=List();for(n=3,1e9,if(try(n), listput(v,n); print(#v" "n))) \\ Charles R Greathouse IV, Feb 20 2017

More terms from Peter J. C. Moses, Feb 09 2017

A332423 If n = Product (p_j^k_j) then a(n) = Sum ((-1)^(k_j + 1) * k_j).

Original entry on oeis.org

0, 1, 1, -2, 1, 2, 1, 3, -2, 2, 1, -1, 1, 2, 2, -4, 1, -1, 1, -1, 2, 2, 1, 4, -2, 2, 3, -1, 1, 3, 1, 5, 2, 2, 2, -4, 1, 2, 2, 4, 1, 3, 1, -1, -1, 2, 1, -3, -2, -1, 2, -1, 1, 4, 2, 4, 2, 2, 1, 0, 1, 2, -1, -6, 2, 3, 1, -1, 2, 3, 1, 1, 1, 2, -1, -1, 2, 3, 1, -3

Offset: 1

Ilya Gutkovskiy, Feb 12 2020

Sum of odd exponents in prime factorization of n minus the sum of even exponents in prime factorization of n.

			a(2700) = a(2^2 * 3^3 * 5^2) = -2 + 3 - 2 = -1.

Cf. A001222, A037916, A067255, A071321, A077761, A195017, A316523, A319273, A332422, A350386, A350387.

a[n_] := Plus @@ ((-1)^(#[[2]] + 1) #[[2]] & /@ FactorInteger[n]); a[1] = 0; Table[a[n], {n, 1, 80}]

a(n) = vecsum(apply(x -> (-1)^(x+1) * x, factor(n)[, 2])); \\ Amiram Eldar, Oct 09 2023

From Amiram Eldar, Oct 09 2023: (Start)
Additive with a(p^e) = (-1)^(e+1) * e.
a(n) = A350387(n) - A350386(n).
Sum_{k=1..n} a(k) ~ n * (log(log(n)) + B - C), where B is Mertens's constant (A077761) and C = Sum_{p prime} (3*p+1)/(p*(p+1)^2) = 0.81918453457738985491 ... . (End)

A079616 Prime factorization templates.

Original entry on oeis.org

0, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 5, 1, 3, 3, 6, 1, 7, 1, 5, 3, 3, 1, 8, 2, 3, 4, 5, 1, 9, 1, 10, 3, 3, 3, 11, 1, 3, 3, 8, 1, 9, 1, 5, 5, 3, 1, 12, 2, 7, 3, 5, 1, 13, 3, 8, 3, 3, 1, 14, 1, 3, 5, 15, 3, 9, 1, 5, 3, 9, 1, 16, 1, 3, 7, 5, 3, 9, 1, 12, 6, 3, 1, 14, 3, 3, 3, 8, 1, 17, 3, 5, 3, 3, 3, 18, 1, 7, 5, 11, 1, 9, 1, 8, 9

Offset: 1

Jon Perry, Jan 29 2003

nonn

0 = 1, 1 = p, 2 = p^2, 3 = p.q, 4 = p^3, 5 = p^2.q, 6 = p^4, 7 = p.q^2, 8 = p^3.q, 9 = p.q.r, 10 = p^5, 11 = p^2.q^2, 12 = p^4.q (p

			Primes are given 1. The next prime factorization pattern is 4=p^2, so a(4)=2 and similarly a(6)=3.

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

Cf. A037916, A077462.

primetemplate(n)=local(f,fl,res,eres); f=factor(n); fl=length(f[,1]); res=""; for (i=1,fl,res=concat(res,f[,2][i])); eres=eval(res); if (v[eres]==0,v[eres]=vc; vc++); eres vc=1; v=vector(10000); for (j=2,50,print1(v[primetemplate(j)]","))

A079616(n) = (A077462(n)-1); \\ Antti Karttunen, Jun 13 2018, uses code in A077462.

a(n) = A077462(n) - 1. - David Wasserman, Dec 21 2004

More terms from David Wasserman, Dec 21 2004

Term a(1) = 0 prepended, superfluous 1 after that removed, extended up to a(105) - Antti Karttunen, Jun 13 2018

A139393 a(n) = Sum_{i=1..m} e(i) * 10^(m-i) where e(1) <= ... <= e(m) are the nonzero exponents in the prime factorization of n: a representation of the prime signature of n.

Original entry on oeis.org

0, 1, 1, 2, 1, 11, 1, 3, 2, 11, 1, 12, 1, 11, 11, 4, 1, 12, 1, 12, 11, 11, 1, 13, 2, 11, 3, 12, 1, 111, 1, 5, 11, 11, 11, 22, 1, 11, 11, 13, 1, 111, 1, 12, 12, 11, 1, 14, 2, 12, 11, 12, 1, 13, 11, 13, 11, 11, 1, 112, 1, 11, 12, 6, 11, 111, 1, 12, 11, 111, 1, 23, 1, 11, 12, 12, 11, 111

Offset: 1

M. F. Hasler, Apr 17 2008, Apr 19 2008

The sorted sequence of (nonzero) exponents in the prime factorization of a number is called its prime signature. Here this is "approximated" by multiplying them by powers of 10. Up to 2^10 this coincides with the concatenation of these exponents written in base 10 (but that sequence would be "base" specific).

For n >= 1024 one should use a modified definition, replacing 10 with 10^floor(1+log_10(log_2(n))), to avoid ambiguity of the representation.

Antti Karttunen, Table of n, a(n) for n = 1..1023
Eric Weisstein's World of Mathematics, Prime Signature.
Wikipedia, Prime signature.

Cf. A037916, A046523, A101296, A118914.

A139393(n)=sum(i=1,#n=vecsort(factor(n)[,2]),10^(#n-i)*n[i])

A282354 Positive j such that d(j) = d(j + 2*d(j)), where d(j) is the number of divisors of j.

Original entry on oeis.org

3, 6, 7, 13, 14, 19, 20, 24, 26, 27, 32, 37, 38, 40, 43, 54, 57, 60, 63, 67, 69, 72, 74, 77, 79, 84, 85, 86, 87, 88, 97, 103, 108, 109, 111, 114, 115, 125, 126, 127, 132, 133, 134, 136, 138, 154, 158, 163, 170, 174, 177, 193, 194, 200, 201, 204, 205, 206, 209

Offset: 1

Vladimir Shevelev, Feb 13 2017

nonn

The sequence contains the smaller member of every pair of cousin primes (A023200).

The sequence contains no perfect squares. Indeed, let a(m) = k^2 for some m. Then, by the definition, d(k^2 + 2*d(k^2)) = d(k^2). Note that d(k^2) is odd. On the other hand, it is known (cf. A046522) that d(k^2) < 2*k. Hence (k+2)^2 - k^2 = 4*k + 4 > 2*d(k^2). Thus k^2 < k^2 + 2*d(k^2) < (k+2)^2. Since, evidently, k^2 + 2*d(k^2) cannot be (k+1)^2, then k^2 + 2*d(k^2) cannot be a square. Therefore, d(k^2 + 2*d(k^2)) is even, which is a contradiction.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A000005, A025487, A037916, A175304, A282231.

Select[Range@ 210, Function[d, DivisorSigma[0, # + 2 d] == d]@ DivisorSigma[0, #] &] (* Michael De Vlieger, Feb 13 2017 *)

is(n)=my(d=numdiv(n)); d==numdiv(n+2*d) \\ Charles R Greathouse IV, Feb 14 2017

More terms from Peter J. C. Moses, Feb 13 2017

A320390 Prime signature of n (sorted in decreasing order), concatenated.

Original entry on oeis.org

0, 1, 1, 2, 1, 11, 1, 3, 2, 11, 1, 21, 1, 11, 11, 4, 1, 21, 1, 21, 11, 11, 1, 31, 2, 11, 3, 21, 1, 111, 1, 5, 11, 11, 11, 22, 1, 11, 11, 31, 1, 111, 1, 21, 21, 11, 1, 41, 2, 21, 11, 21, 1, 31, 11, 31, 11, 11, 1, 211, 1, 11, 21, 6, 11, 111, 1, 21, 11, 111, 1

Offset: 1

M. F. Hasler, Oct 12 2018

In the variant A037916, the exponents of the prime factorization are concatenated without being sorted first (i.e., rows of A124010).

			For n = 1, the prime signature is the empty sequence, so the concatenation of its terms yields 0 by convention.
For n = 2 = 2^1, n = 3 = 3^1 and any prime p = p^1, the prime signature is (1), and concatenation yields a(n) = 1.
For n = 4 = 2^2, the prime signature is (2), and concatenation yields a(n) = 2.
For n = 6 = 2^1 * 3^1, the prime signature is (1,1), and concatenation yields a(n) = 11.
For n = 12 = 2^2 * 3^1 but also n = 18 = 2^1 * 3^2, the prime signature is (2,1) since exponents are sorted in decreasing order; concatenation yields a(n) = 21.
For n = 30 = 2^1 * 3^1 * 5^1, the prime signature is (1,1,1), and concatenation yields a(n) = 111.
For n = 3072 = 2^10 * 3^1, the prime signature is (10,1), and concatenation yields a(n) = 101. This is the first term with nondecreasing digits.

Cf. A037916, A118914, A124010, A212171.

{0}~Join~Array[FromDigits@ Flatten[IntegerDigits /@ FactorInteger[#][[All, -1]] ] &, 78, 2] (* Michael De Vlieger, Oct 13 2018 *)

a(n)=fromdigits(vecsort(factor(n)[,2]~,,4)) \\ Except for multiples of 2^10, 3^10, etc.

a(n)=eval(concat(apply(t->Str(t),vecsort(factor(n)[,2]~,,4)))) \\ Slower but correct for all n.

a(n) = concatenation of row n of A212171.

a(n) = a(A046523(n)). - David A. Corneth, Oct 13 2018

A329025 If n = Product (p_j^k_j) then a(n) = concatenation (pi(p_j)), where pi = A000720.

Original entry on oeis.org

0, 1, 2, 1, 3, 12, 4, 1, 2, 13, 5, 12, 6, 14, 23, 1, 7, 12, 8, 13, 24, 15, 9, 12, 3, 16, 2, 14, 10, 123, 11, 1, 25, 17, 34, 12, 12, 18, 26, 13, 13, 124, 14, 15, 23, 19, 15, 12, 4, 13, 27, 16, 16, 12, 35, 14, 28, 110, 17, 123, 18, 111, 24, 1, 36, 125, 19, 17, 29, 134

Offset: 1

Ilya Gutkovskiy, Nov 02 2019

Concatenate of indices of distinct prime factors of n, in increasing order.

			a(60) = a(2^2 * 3 * 5) = a(prime(1)^2 * prime(2) * prime(3)) = 123.

Ilya Gutkovskiy, Scatter plot of a(n) up to n=100000
Index entries for sequences computed from indices in prime factorization

Cf. A000720, A037916, A080695, A084317, A127668, A304038, A329026.

a[n_] := FromDigits[Flatten@IntegerDigits@(PrimePi[#[[1]]] & /@ FactorInteger[n])]; Table[a[n], {n, 1, 70}]

a(prime(n)^k) = n for k > 0.

A227815 Composite numbers n divisible by their concatenated exponents in prime factorization.

Original entry on oeis.org

4, 16, 22, 27, 33, 55, 63, 77, 143, 187, 209, 222, 248, 253, 256, 319, 341, 407, 451, 473, 484, 517, 555, 583, 649, 656, 671, 737, 777, 781, 803, 837, 869, 913, 979, 1067, 1111, 1133, 1152, 1177, 1199, 1221, 1243, 1397, 1441, 1443, 1507, 1529, 1639, 1661, 1727

Offset: 1

Michel Lagneau, Jul 31 2013

The numbers 2^(2^m), m = 1, 2,... are in the sequence. A majority of semiprimes of the form 11*p where is p prime different from 11 are in the sequence. The numbers of the form p*111 = p*3*37 where p is prime different from 3 or 37 are in the sequence. In the general case, the numbers of the form n = p_1*p_2*...*p_m*R where the p_k are prime numbers and R is a repunit number (A002275) with q digits "1" and (q-m) prime divisors are in the sequence, for example the numbers of the form n = p_1*p_2*p_3*p_4*11111111 = p_1*p_2*p_3*p_4*11*73*101*137 are in the sequence if the primes p_k are different from 11, 73, 101 or 137. So, 11111111 divides n.

			248 = 2^3*31 => 31 is the concatenate exponents 3 and 1, so 31 divides 248.

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A002275, A037916, A070529.

with(numtheory):for n from 1 to 10000 do:x:=ifactors(n):y:=x[2];n1:=nops(y):s:=0:for i from 1 to n1 do:z:=y[i][2]:s:=s+z*10^(n1-i):od:if type(n,prime)=false and irem(n,s)=0 then printf(`%d, `, n):else fi:od:

With[{predicate = And[CompositeQ[#], Divisible[#, FromDigits[Join @@ IntegerDigits@(Last /@ FactorInteger[#])]]] &},
Select[Range[10000], predicate]] (* Sidney Cadot, Feb 19 2023 *)

from sympy import isprime, factorint
def ok(n): return n > 1 and not isprime(n) and n%int("".join(str(e) for e in factorint(n).values())) == 0
print([k for k in range(1728) if ok(k)]) # Michael S. Branicky, Feb 19 2023

Showing 1-10 of 15 results. Next

cp's OEIS Frontend

A342679 Number of steps for n to reach 1 or n by repeated application of A037916, or -1 if they are never reached.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Python

A077462 Prime factor configuration patterns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A282231 First term of A175304 with a given prime signature.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A332423 If n = Product (p_j^k_j) then a(n) = Sum ((-1)^(k_j + 1) * k_j).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A079616 Prime factorization templates.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A139393 a(n) = Sum_{i=1..m} e(i) * 10^(m-i) where e(1) <= ... <= e(m) are the nonzero exponents in the prime factorization of n: a representation of the prime signature of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A282354 Positive j such that d(j) = d(j + 2*d(j)), where d(j) is the number of divisors of j.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica