A023503 -id:A023503 - cp's OEIS frontend

A337775 a(n) is the least natural k which is a multiple of prime(n) such that for some m >= 0, phi(k) = rad(k)^m, where phi(k) = A000010(k) and rad(k) = A007947(k).

2, 18, 250, 6174, 3660250, 1542294, 2839714, 41154, 117793122328750, 7978057537338, 2898701538750, 33734898, 29688151506250, 21107677374, 69834458642125879757481250, 3999523458421521342

Offset: 1

Vladislav Shubin, Sep 20 2020

nonn

The number m mentioned above is usually referred to as the order of the corresponding number a(n). The sequence of these orders is in A337776.
The algorithm suggested here for the calculation of a(n) starts its work from prime(n).
Numbers k such that phi(k) = rad(k)^m with m >= 1 are given in A211413. - Andrew Howroyd, Sep 21 2020

			For n=12 the initial prime is prime(12) = 37 and a(12) = 33734898 because phi(33734898) = 10941048, rad(33734898) = 222 and 222^3 = 10941048 and there is no smaller number satisfying the requirements. The order of a(12) is 3.

J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 108, p. 38, Ellipses, Paris 2008.
J.-M. De Koninck & A. Mercier, 1001 Problèmes en Théorie Classique Des Nombres, Problème 745 ; pp 95; 317-8, Ellipses Paris 2004.

J.-M. De Koninck, When the Totient Is the Product of the Squared Prime Divisors: Problem 10966, Amer. Math. Monthly, 111 (2004), p. 536.

Cf. A000010 (phi), A000040 (prime), A007947 (rad), A023503, A024619, A105261, A211413.

nn = 16;
Sar = Table[0, {nn}]; Sar[[1]] = 2;
(*It is a list oh the sequence A337775*)
OrdSar = Table[0, {nn}]; OrdSar[[1]] = 0;
(*It is a sequence A337776 - the orders of members in sequence A337775*) For[Index = 2, Index <= nn, Index++,
  InitialPrime = Prime[Index];
  InitialInteger = InitialPrime - 1;
  InitialArray = FactorInteger[InitialInteger];
  For[i = 1, i <= Length[InitialArray], i++,
   CurrentArray =
    FactorInteger[InitialArray[[-i, 1]] - 1] ~Join~ InitialArray;
   InitialInterger =
    Product[CurrentArray[[k, 1]] ^ CurrentArray[[k, 2]], {k, 1,
      Length[CurrentArray]}];
     InitialArray = FactorInteger[InitialInterger];
   ];
  InitialArray = InitialArray ~Join~ {{InitialPrime, 0}};
  Ord = Max[InitialArray[[All, 2]]];
  Lint = Product[
    Power[InitialArray[[k, 1]], Ord - InitialArray[[k, 2]] + 1], {k,
     1, Length[InitialArray]}];
  radn = Product[InitialArray[[k, 1]], {k, 1, Length[InitialArray]}];
  Sar[[Index]] = Lint;
  OrdSar[[Index]] = Ord;
  ];
Print["Sar=  ", Sar]
Print["OrdSar=  ", OrdSar]

rad(n) = factorback(factorint(n)[, 1]);
isok(k) = my(phik=eulerphi(k), radk=rad(k), x=logint(phik, radk)); radk^x == phik;
a(n) = {my(p=prime(n), k=p); while (!isok(k), k+=p); k;} \\ Michel Marcus, Sep 23 2020

A061638 Primes p such that the greatest prime divisor of p-1 is 7.

Original entry on oeis.org

29, 43, 71, 113, 127, 197, 211, 281, 337, 379, 421, 449, 491, 631, 673, 701, 757, 883, 1009, 1051, 1373, 1471, 2017, 2269, 2521, 2647, 2689, 2801, 3137, 3361, 3529, 4201, 4481, 5881, 6301, 7001, 7057, 7351, 7561, 7841, 8233, 8821, 10501, 10753, 12097

Offset: 1

Labos Elemer, Jun 13 2001

nonn

Prime numbers n for which cos(2*Pi/n) is an algebraic number of 7th degree. - Artur Jasinski, Dec 13 2006

			For n = {4, 8, 9, 12}, a(n)-1 = {70, 210, 280, 420} = 7*{10, 30, 40, 60}.

Harry J. Smith and Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 500 terms from Smith)

The 4th in a family of sequences after A019434(=Fermat-primes), A058383, A061599.
Cf. A019434, A058383, A023503, A034694, A006530, A006093, A035095, A061599.
Cf. A004729, A058383, A125867-A125875, A024899.

Select[Prime[Range[2000]],FactorInteger[#-1][[-1,1]] ==7&]  (* Harvey P. Dale, Mar 12 2011 *)

default(primelimit, 108864001); n=0; forprime (p=3, 108864001, f=factor(p - 1)~; if (f[1, length(f)]==7, write("b061638.txt", n++, " ", p))) \\ Harry J. Smith, Jul 25 2009

list(lim)=my(v=List(), t, t5, t7); lim\=1; lim--; for(a=1, logint(lim\2, 7), t7=2*7^a; for(b=0, logint(lim\t7, 5), t5=5^b*t7; for(c=0, logint(lim\t5, 3), t=3^c*t5; while(t<=lim, if(isprime(t+1), listput(v, t+1)); t<<=1)))); Set(v) \\ Charles R Greathouse IV, Oct 29 2018

Primes of form 2^a*3^b*5^c*7^d + 1 with a and d > 1.

A085378 Difference between primes p and the largest prime divisor of p-1.

Original entry on oeis.org

3, 4, 6, 10, 15, 16, 12, 22, 26, 34, 36, 36, 24, 40, 30, 56, 56, 64, 70, 66, 42, 78, 94, 96, 86, 54, 106, 106, 120, 118, 120, 116, 112, 146, 144, 160, 84, 130, 90, 176, 172, 190, 190, 188, 204, 186, 114, 210, 204, 222, 236, 246, 255, 132, 202, 266, 254, 274, 236

Offset: 3

Cino Hilliard, Aug 12 2003

This sequence contains only one prime number, the 3.

			For prime 107 we have 107 - 53 = 54.

A085378 := proc(n)
    ithprime(n)-A023503(n) ;
end proc:
seq( A085378(n),n=3..80) ; # R. J. Mathar, Sep 07 2016

#-FactorInteger[#-1][[-1,1]]&/@Prime[Range[3,70]] (* Harvey P. Dale, Jan 04 2012 *)

cminuspm1(n) = \ prime - maxprime of prime-1 { forprime(x=5,n, forstep(p=x,2,-1, if(isprime(p) & (x-1)%p==0,print1(x-p,","); break); ) ) }

A260360 The absolute difference between the largest prime factors of prime(n)-1 and prime(n+1)-1.

Original entry on oeis.org

0, 1, 2, 2, 1, 1, 8, 4, 2, 2, 2, 2, 16, 10, 16, 24, 6, 4, 4, 10, 28, 30, 8, 2, 12, 36, 50, 4, 0, 6, 4, 6, 14, 32, 8, 10, 80, 40, 46, 84, 14, 16, 4, 4, 4, 30, 76, 94, 10, 12, 12, 0, 3, 129, 64, 62, 18, 16, 40, 26, 56, 14, 18, 66, 68, 4, 166, 144, 18, 168, 118, 30, 24, 184, 94, 86, 6, 12, 2, 12, 36, 40, 70, 56, 10

Offset: 2

Pratik Koirala, Otis Tweneboah, Nathan Fox, Eugene Fiorini, Jul 23 2015

nonn

a(n)=0 if and only if n is in A105403.

It is an open question whether there are infinitely many zeros in this sequence. Are there infinitely many terms below some fixed upper bound?

			n=4: The prime factors of prime(4)-1 are 2,3 and the prime factors of prime(5)-1 are 2,5. The largest are 3 and 5, so a(4)=2.

Robert Israel, Table of n, a(n) for n = 2..10000

Cf. A023503, A105403.

B:= [seq(max(numtheory:-factorset(ithprime(i)-1)),i=2..101)]:
seq(abs(B[n+1]-B[n]),n=1..99); # Robert Israel, Aug 06 2015

Table[Abs[FactorInteger[Prime[n] - 1][[-1, 1]] - FactorInteger[Prime[n + 1] - 1][[-1, 1]]], {n, 2, 86}] (* Michael De Vlieger, Jul 24 2015 *)
Rest[Abs[Differences[Table[FactorInteger[p-1][[-1,1]],{p,Prime[ Range[ 90]]}]]]] (* Harvey P. Dale, Aug 08 2021 *)

gpf(n) = if(n>1, vecmax(factor(n)[, 1]), 1);
a(n) = gpf(prime(n)-1) - gpf(prime(n+1)-1); \\ Michel Marcus, Aug 05 2015

a(n) = abs(A023503(n+1) - A023503(n)). - Robert Israel, Aug 06 2015

A371924 a(n) is the least b such that prime(n)-1 divides b!.

Original entry on oeis.org

1, 2, 4, 3, 5, 4, 6, 6, 11, 7, 5, 6, 5, 7, 23, 13, 29, 5, 11, 7, 6, 13, 41, 11, 8, 10, 17, 53, 9, 7, 7, 13, 17, 23, 37, 10, 13, 9, 83, 43, 89, 6, 19, 8, 14, 11, 7, 37, 113, 19, 29, 17, 6, 15, 10, 131, 67, 9, 23, 7, 47, 73, 17, 31, 13, 79, 11, 7, 173, 29, 11

Offset: 1

Samuel Harkness, Apr 12 2024

nonn

This list is connected to Pollard's p-1 algorithm, using the version of the algorithm iterating over all positive integers. Say a large number m has two distinct prime factors q and r, and using Pollard's p-1 algorithm someone wishes to obtain the prime factors. Say q = 223 and r = 307. As prime(48) = 223 and a(48) = 37, given a random "a" coprime to m the factor 223 will be discovered in 37 steps. Also, as prime(63) = 307 and a(63) = 17, given a random "a" coprime to m the factor 307 will be discovered in 17 steps. Note that after 37 steps both factors will be discovered, so the algorithm will return m, failing to discover either prime factor. Therefore, when 17 <= b < 37 the prime factor 307 will be discovered. Note that on rare occasions, for a given "a" value, by chance p divides (a^b! - 1), so it is possible that for some "a" values the actual b value will be less. But, for any "a" value and prime p = prime(n), it is guaranteed that b <= a(n).

			For n = 25, prime(25) = 97, so we will use p = 97. Then the prime factorization of p - 1  is p - 1 = 2^5 * 3. Note that for p - 1 to divide b!, the exponents for all prime factors in b! must be greater than or equal to the exponents for all prime factors in the prime factorization of p - 1. We find that 8! = 2^7 * 3^2 * 5 * 7 is the least b such that this is true, so a(25) = 8.

Samuel Harkness, Table of n, a(n) for n = 1..10000
Wikipedia, Pollard's p-1 algorithm

Cf. A000040, A002034, A023503, A092965.

a371924[p_] :=
 Module[{a, d, f, u, v}, f = FactorInteger[p - 1]; d = {};
  For[a = 1, a <= Length[f], a++,
   u = f[[a]];
   v = u[[1]]^u[[2]];
   i = 1;
   While[! Divisible[(u[[1]]*i)!, v], i++]; AppendTo[d, u[[1]]*i]];
  Return[Max[d]]]
list = {};
For[p = 1, p <= 71, p++,
 AppendTo[list, {p, a371924[Prime[p]]}]]
Print[list]

a(n) = my(b=1, q=prime(n)-1); while (b! % q, b++); b; \\ Michel Marcus, Apr 15 2024

from sympy import prime
def A371924(n):
    m = prime(n)-1
    b, k = 1, 1%m
    while k:
        b += 1
        k = k*b%m
    return b # Chai Wah Wu, Apr 25 2024

A379445 a(n) = gpf(prime(n)-1)*gpf(prime(n)+1), where gpf is A006530.

Original entry on oeis.org

4, 6, 6, 15, 21, 6, 15, 33, 35, 10, 57, 35, 77, 69, 39, 145, 155, 187, 21, 111, 65, 287, 55, 21, 85, 221, 159, 33, 133, 14, 143, 391, 161, 185, 95, 1027, 123, 581, 1247, 445, 65, 57, 291, 77, 55, 371, 259, 2147, 437, 377, 85, 55, 35, 86, 1441, 335, 85, 3197, 329, 3337

Offset: 2

Hugo Pfoertner, Dec 28 2024

nonn

Observation: Even terms of A006881 not occurring in this sequence are, e.g., 22, 34, 38, 46, ..., due to the sparseness of Mersenne primes (A000668) and Fermat primes (A000215). Also missing are many multiples of 3, e.g., 3*{31, 67, 79, 83, 101, 103, 113, ...}, as a consequence of the gaps of A058383 and A268640 and the size distribution of prime factors, i.e., the rareness of smooth numbers.

			a(43390) = 146 because 2^19-1 = A000668(5) is the 43390th prime and the greatest prime factor of 2^19-2 is 73.

Hugo Pfoertner, Table of n, a(n) for n = 2..10000
Hugo Pfoertner, 1 million terms of A379445, 7z compressed file (5 MB) (2025).

Cf. A006530, A023503, A023509, A087713.
Each term > 4 is element of A006881.
Cf. A000215, A000668, A058383, A268640.

Table[Times @@ Map[FactorInteger[#][[-1, 1]] &, Prime[n] + {-1, 1}], {n, 2, 61}] (* Michael De Vlieger, Jan 20 2025 *)

a379445(n) = my (p=prime(n), fm=factor(p-1), fp=factor(p+1)); fm[#fm~,1]*fp[#fp~,1]

a(n) = A023503(n)*A023509(n). - Michel Marcus, Jan 21 2025

A085382 Sum of p = prime(n) and largest prime divisor of p-1.

Original entry on oeis.org

5, 7, 10, 16, 16, 19, 22, 34, 36, 36, 40, 46, 50, 70, 66, 88, 66, 78, 78, 76, 92, 124, 100, 100, 106, 120, 160, 112, 120, 134, 144, 154, 162, 186, 156, 170, 166, 250, 216, 268, 186, 210, 196, 204, 210, 218, 260, 340, 248, 262, 256, 246, 256, 259, 394, 336, 276, 300

Offset: 2

Cino Hilliard, Aug 12 2003

			a(2) = prime(2) + gpf(prime(2) - 1) = 3 + gpf(2) = 3 + 2 = 5.

Cf. A006530, A023503, A274022.

cminuspm2(n) = \\ prime + maxprime of prime-1
{ forprime(x=5,n, forstep(p=x,2,-1, if(isprime(p) & (x-1)%p==0,print1(x+p,","); break); ) ) }

a(n) = my(p=prime(n)); p+vecmax(factor(p-1)[,1]); \\ Michel Marcus, May 07 2024

a(n) = p + A006530(p-1) where p = prime(n).

Offset 2 and a(2) from Michel Marcus, May 07 2024

Edited by Jon E. Schoenfield, May 07 2024

A174870 Odd indices m for which A174869(m) is <>1.

Original entry on oeis.org

1, 9, 21, 25, 27, 33, 45, 57, 75, 77, 81, 85, 91, 93, 105, 115, 117, 121, 125, 133, 135, 141, 145, 147, 165, 169, 171, 175, 177, 187, 189, 201, 205, 213, 217, 221, 225, 231, 235, 243, 245, 247, 253, 261, 273, 275, 289, 297, 301, 315, 325, 333, 343, 345, 355, 357, 361, 363

Offset: 1

Vladimir Shevelev, Mar 31 2010

nonn

All but the first term in the sequence are composite numbers.

			The 9 refers to A174869(9) = 7. The 21 refers to A174869(21) = 3.

Cf. A174869, A006530, A103667, A023503, A023509, A174857, A020639 ,A002618, A036689.

More terms from R. J. Mathar, Aug 10 2010

cp's OEIS Frontend

A337775 a(n) is the least natural k which is a multiple of prime(n) such that for some m >= 0, phi(k) = rad(k)^m, where phi(k) = A000010(k) and rad(k) = A007947(k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A061638 Primes p such that the greatest prime divisor of p-1 is 7.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A085378 Difference between primes p and the largest prime divisor of p-1.

Views

Author

Keywords

Comments

Examples

Programs

Maple

Mathematica

PARI

A260360 The absolute difference between the largest prime factors of prime(n)-1 and prime(n+1)-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A371924 a(n) is the least b such that prime(n)-1 divides b!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

A379445 a(n) = gpf(prime(n)-1)*gpf(prime(n)+1), where gpf is A006530.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A085382 Sum of p = prime(n) and largest prime divisor of p-1.

Views

Author

Keywords

Examples

Crossrefs

Programs