A172999 -id:A172999 - cp's OEIS frontend

A178442 Two numbers k and l we call equivalent if they have the same vector of exponents with positive components in prime power factorization. Let a(1)=1, a(2)=3. Then a(n)>a(n-1) is the smallest number equivalent to n.

1, 3, 5, 9, 11, 14, 17, 27, 49, 51, 53, 63, 67, 69, 74, 81, 83, 98, 101, 116, 118, 119, 127, 135, 169, 177, 343, 356, 359, 366, 367, 3125, 3127, 3131, 3133, 3249, 3251, 3254, 3261, 3272, 3299, 3302, 3307, 3308, 3316, 3317, 3319, 3321, 3481

Offset: 1

Vladimir Shevelev, Dec 22 2010

nonn

Note that, e.g., 12 and 50 have similar structure in their prime power factorizations, but are not equivalent: their vectors of exponents are (2,1) and (1,2). On the other hand, 6 and 35 are equivalent with the same vector (1,1).

Question. What is the growth of the sequence?

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

Cf. A172980, A172999

nxt[{n_,a_}]:=Module[{j=FactorInteger[n+1][[All,2]],k=a+1},While[ j!= FactorInteger[k][[All,2]],k++];{n+1,k}]; Join[{1},NestList[nxt,{2,3},50][[All,2]]] (* Harvey P. Dale, Jul 03 2020 *)

prime_signature = lambda n: [m for p, m in factor(n)]
@CachedFunction
def A178442(n):
    if n <= 2: return {1:1, 2:3}[n]
    psig_n = prime_signature(n)
    return next(k for k in IntegerRange(A178442(n-1)+1,infinity) if prime_signature(k) == psig_n)
# D. S. McNeil, Dec 22 2010

Corrected and extended by D. S. McNeil, Dec 22 2010

A178443 Two numbers k and l we call equivalent if they have the same vector of exponents with positive components in prime power factorization. Let a(1)=1, a(2)=3. If n>=3 is prime, then a(n) is the smallest prime greater than a(n-1); otherwise, a(n)>a(n-1) is the smallest number equivalent to n such that prime power factorization of a(n) contains only primes which already appeared in the sequence.

Original entry on oeis.org

1, 3, 5, 9, 11, 15, 17, 27, 121, 187, 191, 275, 277, 573, 831, 14641, 14653, 109443, 109451, 131877, 161183, 249101, 249103, 254221, 214710409, 1603785503, 3146151623077, 23500268975459, 23500268975497, 352504034632455, 352504034632459, 675511501766876508493, 8283939628810696270871857123

Offset: 1

Vladimir Shevelev, Dec 22 2010

The sequence contains exactly 33 terms.

			By the condition, a(12) should be more than a(11)=191. Since 12 has vector of positive exponents (2,1), then we seek already constructed prime terms p<q in the sequence and choose the smallest number of the form p^2*q>191. It is 275=5^2*11. Thus a(12)=275. Further, a(13) should be the nearest prime more than 275. It is 277.

Cf. A178442, A172980, A172999

@CachedFunction
def A178443(n):
    if n <= 2: return {1:1, 2:3}[n]
    if is_prime(n): return next_prime(A178443(n-1))
    psig_n = list(m for p,m in factor(n))
    primes_seen = sorted(set(filter(is_prime, map(A178443, range(2,n)))))
    possibles = (prod(p**m for p,m in zip(pvec, psig_n)) for pvec in Combinations(primes_seen, len(psig_n)))
    return min(p for p in possibles if p > A178443(n-1))
# D. S. McNeil, Jan 01 2011

A173381 a(n) = b_n(p_(n+1)) where p_n is the n-th prime, b_n(1)=1, b_n(2)=p_n, and for k>=3, b_n(k) is the smallest number larger than b_n(k-1) such that, for all i

Original entry on oeis.org

3, 11, 31, 163, 661, 929, 2041, 21341, 15989, 47387, 125117, 263411, 123493, 10426601, 3654221, 4167127, 86622397, 4036267, 3910993, 541513877

Offset: 1

Vladimir Shevelev, Nov 22 2010

nonn

Cf. A000040, A172980, A172999.

b:= proc(n, k) option remember; local ok, m, i;
      if k=1 then 1
    elif k=2 then ithprime(n)
    else for m from b(n, k-1)+1 do
           ok:= true;
           for i from 1 to k-1 do
             if igcd(k, i)=1 xor igcd(m, b(n, i))=1
                then ok:= false; break fi
           od;
           if ok then break fi
         od; m
      fi
    end:
a:= n-> b(n, ithprime(n+1));
seq(a(n), n=1..10);  # Alois P. Heinz, Nov 22 2010

b[n_, k_] := b[n, k] = Module[{ok, m, i}, Which[k==1, 1, k==2, Prime[n], True, For[m = b[n, k - 1] + 1, True, m++, ok = True; For[i = 1, i <= k - 1, i++, If[Xor[GCD[k, i]==1, GCD[m, b[n, i]]==1],  ok = False; Break[]]]; If[ok, Break[]]]; m]];
a[n_] := b[n, Prime[n + 1]];
Array[a, 10] (* Jean-François Alcover, Nov 28 2020, after Alois P. Heinz *)

More terms from Alois P. Heinz, Nov 22 2010

cp's OEIS Frontend

A178442 Two numbers k and l we call equivalent if they have the same vector of exponents with positive components in prime power factorization. Let a(1)=1, a(2)=3. Then a(n)>a(n-1) is the smallest number equivalent to n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Sage

Extensions

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Sage

A173381 a(n) = b_n(p_(n+1)) where p_n is the n-th prime, b_n(1)=1, b_n(2)=p_n, and for k>=3, b_n(k) is the smallest number larger than b_n(k-1) such that, for all i

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

Extensions