A235138 -id:A235138 - cp's OEIS frontend

A007850 Giuga numbers: composite numbers n such that p divides n/p - 1 for every prime divisor p of n.

30, 858, 1722, 66198, 2214408306, 24423128562, 432749205173838, 14737133470010574, 550843391309130318, 244197000982499715087866346, 554079914617070801288578559178, 1910667181420507984555759916338506

Offset: 1

D. Borwein, J. M. Borwein, P. B. Borwein and R. Girgensohn

There are no other Giuga numbers with 8 or fewer prime factors. I did an exhaustive search using a PARI script which implemented Borwein and Girgensohn's method for finding n factor solutions given n - 2 factors. - Fred Schneider, Jul 04 2006
One further Giuga number is known with 10 prime factors, namely:
420001794970774706203871150967065663240419575375163060922876441614\
2557211582098432545190323474818 =
2 * 3 * 11 * 23 * 31 * 47059 * 2217342227 * 1729101023519 * 8491659218261819498490029296021 * 58254480569119734123541298976556403 but this may not be the next term. (See the Butske et al. paper.)
Conjecture: Giuga numbers are the solution of the differential equation n' = n + 1, where n' is the arithmetic derivative of n. - Paolo P. Lava, Nov 16 2009
n is a Giuga number if and only if n' = a*n + 1 for some integer a > 0 (see our preprint in arXiv:1103.2298). - José María Grau Ribas, Mar 19 2011
A composite number n is a Giuga number if and only if Sum_{i = 1..n-1} i^phi(n) == -1 (mod n), where phi(n) = A000010(n). - Jonathan Sondow, Jan 03 2014
A composite number n is a Giuga number if and only if Sum_{prime p|n} 1/p = 1/n + an integer. (In fact, all known Giuga numbers n satisfy Sum_{prime p|n} 1/p = 1/n + 1.) - Jonathan Sondow, Jan 08 2014
The prime factors of a(n) are listed as n-th row of A236434. - M. F. Hasler, Jul 13 2015
Conjecture: let k = a(n) and k be the product of x(n) distinct prime factors where x(n) <= x(n+1). Then, for any even n, n/2 + 2 <= x(n) <= n/2 + 3 and, for any odd n, (n+1)/2 + 2 <= x(n) <= (n+1)/2 + 3. For any n > 1, there are y "old" distinct prime factors o(1)...o(y) such that o(1) = 2, o(2) = 3, and z "new" distinct prime factors n(1)...n(z) such that none of them - unlike the "old" ones - can be a divisor of a(q) while q < n; n(1) > o(y), y = x(n) - z >= 2, 2 <= z <= b where b is either 4, or 1/2*n. - Sergey Pavlov, Feb 24 2017
Conjecture: a composite n is a Giuga number if and only if Sum_{k=1..n-1} k^lambda(n) == -1 (mod n), where lambda(n) = A002322(n). - Thomas Ordowski and Giovanni Resta, Jul 25 2018
A composite number n is a Giuga number if and only if A326690(n) = 1. - Jonathan Sondow, Jul 19 2019
A composite n is a Giuga number if and only if n * A027641(phi(n)) == - A027642(phi(n)) (mod n^2). Note: Euler's phi function A000010 can be replaced by the Carmichael lambda function A002322. - Thomas Ordowski, Jun 07 2020
By von Staudt and Clausen theorem, a composite n is a Giuga number if and only if n * A027759(phi(n)) == A027760(phi(n)) (mod n^2). Note: Euler's phi function can be replaced by the Carmichael lambda function. - Thomas Ordowski, Aug 01 2020

			From _M. F. Hasler_, Jul 13 2015: (Start)
The prime divisors of 30 are {2, 3, 5}, and 2 divides 30/2-1 = 14, 3 divides 30/3-1 = 9, and 5 divides 30/5-1 = 5.
The prime divisors of 858 are {2, 3, 11, 13} and 858/2-1 = 428 is even, 858/3-1 = 285 is divisible by 3, 858/11-1 = 77 is a multiple of 11, and 858/13-1 = 65 = 13*5.
(End)

J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 30, pp 11, Ellipses, Paris 2008.

M. A. Alekseyev, J. M. Grau, A. M. Oller-Marcen. Computing solutions to the congruence 1^n + 2^n + ... + n^n == p (mod n). Discrete Applied Mathematics, 2018. doi:10.1016/j.dam.2018.05.022 arXiv:1602.02407 [math.NT], 2016.
D. Borwein, J. M. Borwein, P. B. Borwein and R. Girgensohn, Giuga's Conjecture on Primality, Amer. Math. Monthly 103, No. 1, 40-50 (1996).
J. M. Borwein and E. Wong, A Survey of Results Relating to Giuga's Conjecture on Primality, Vinet, Luc (ed.): Advances in Mathematical Sciences: CRM's 25 Years. Providence, RI: American Mathematical Society. CRM Proc. Lect. Notes. 11, 13-27 (1997).
William Butske, Lynda M. Jaje, and Daniel R. Mayernik, On the equation Sum_{p | N} 1/p + (1/N)=1, pseudoperfect numbers and perfectly weighted graphs, Math. Comp. 69 (2000), no. 229, 407-420.
José María Grau and Antonio M. Oller-Marcén, Giuga Numbers and the arithmetic derivative., arXiv:1103.2298 [math.NT], 2011; J. Int. Seq. 15 (2012) 12.4.1
José María Grau and Antonio M. Oller-Marcén, Generalizing Giuga's conjecture, arXiv:1103.3483 [math.NT], 2011.
J. M. Grau and A. M. Oller-Marcén, On the congruence sum_{j=1}^{n-1} j^{k(n-1)} == -1 (mod n); k-strong Giuga and k-Carmichael numbers, arXiv preprint arXiv:1311.3522 [math.NT], 2013.
J. M. Grau, A. M. Oller-Marcén, and D. Sadornil, On µ-Sondow Numbers, arXiv:2111.14211 [math.NT], 2021.
John Machacek, Egyptian Fractions and Prime Power Divisors, arXiv:1706.01008 [math.NT], 2017.
Mersenne Forum, Giuga numbers
Romeo Meštrović, Generalizations of Carmichael numbers I, arXiv:1305.1867 [math.NT], May 04 2013.
R. Mestrovic, On a Congruence Modulo n^3 Involving Two Consecutive Sums of Powers, Journal of Integer Sequences, Vol. 17 (2014), 14.8.4.
J. Sondow and K. MacMillan, Primary pseudoperfect numbers, arithmetic progressions, and the Erdős-Moser equation, Amer. Math. Monthly, 124 (2017) 232-240; arXiv:math/1812.06566 [math.NT], 2018.
J. Sondow and E. Tsukerman, The p-adic order of power sums, the Erdos-Moser equation, and Bernoulli numbers, arXiv:1401.0322 [math.NT], 2014; see section 4.
Eric Weisstein's World of Mathematics, Giuga Number.
Wikipedia, Agoh-Giuga conjecture
Wikipedia, Giuga number

Cf. A054377, A216823, A216824, A235137, A235138, A235140, A235363, A236434, A326690.

fQ[n_] := AllTrue[First /@ FactorInteger@ n, Divisible[n/# - 1, #] &]; Select[Range@ 100000, CompositeQ@ # && fQ@ # &] (* Michael De Vlieger, Oct 05 2015 *)

is(n)=if(isprime(n), return(0)); my(f=factor(n)[,1]); for(i=1,#f, if((n/f[i])%f[i]!=1, return(0))); n>1 \\ Charles R Greathouse IV, Apr 28 2015

from itertools import count, islice
from sympy import isprime, primefactors
def A007850_gen(startvalue=2): # generator of terms >= startvalue
    return filter(lambda x: not isprime(x) and all((x//p-1) % p == 0 for p in primefactors(x)), count(max(startvalue,2)))
A007850_list = list(islice(A007850_gen(),4)) # Chai Wah Wu, Feb 19 2022

Sum_{i = 1..a(n)-1} i^phi(a(n)) == -1 (mod a(n)). - Jonathan Sondow, Jan 03 2014

a(12) from Fred Schneider, Jul 04 2006
Further references from Fred Schneider, Aug 19 2006
Definition corrected by Jonathan Sondow, Sep 16 2012

A054377 Primary pseudoperfect numbers: numbers n > 1 such that 1/n + sum 1/p = 1, where the sum is over the primes p | n.

Original entry on oeis.org

2, 6, 42, 1806, 47058, 2214502422, 52495396602, 8490421583559688410706771261086

Offset: 1

Eric W. Weisstein

Primary pseudoperfect numbers are the solutions of the "differential equation" n' = n-1, where n' is the arithmetic derivative of n. - Paolo P. Lava, Nov 16 2009
Same as n > 1 such that 1 + sum n/p = n (and the only known numbers n > 1 satisfying the weaker condition that 1 + sum n/p is divisible by n). Hence a(n) is squarefree, and is pseudoperfect if n > 1. Remarkably, a(n) has exactly n (distinct) prime factors for n < 9. - Jonathan Sondow, Apr 21 2013
From the Wikipedia article: it is unknown whether there are infinitely many primary pseudoperfect numbers, or whether there are any odd primary pseudoperfect numbers. - Daniel Forgues, May 27 2013
Since the arithmetic derivative of a prime p is p' = 1, 2 is obviously the only prime in the sequence. - Daniel Forgues, May 29 2013
Just as 1 is not a prime number, 1 is also not a primary pseudoperfect number, according to the original definition by Butske, Jaje, and Mayernik, as well as Wikipedia and MathWorld. - Jonathan Sondow, Dec 01 2013
Is it always true that if a primary pseudoperfect number N > 2 is adjacent to a prime N-1 or N+1, then in fact N lies between twin primes N-1, N+1? See A235139. - Jonathan Sondow, Jan 05 2014
Also, integers n > 1 such that A069359(n) = n - 1. - Jonathan Sondow, Apr 16 2014

			From _Daniel Forgues_, May 24 2013: (Start)
With a(1) = 2, we have 1/2 + 1/2 = (1 + 1)/2 = 1;
with a(2) = 6 = 2 * 3, we have
  1/2 + 1/3 + 1/6 = (3 + 2 + 1)/6 = (1*3 + 3)/(2*3) = (1 + 1)/2 = 1;
with a(3) = 42 = 6 * 7, we have
  1/2 + 1/3 + 1/7 + 1/42 = (21 + 14 + 6 + 1)/42 =
  (3*7 + 2*7 + 7)/(6*7) = (3 + 2 + 1)/6 = 1;
with a(4) = 1806 = 42 * 43, we have
  1/2 + 1/3 + 1/7 + 1/43 + 1/1806 = (903 + 602 + 258 + 42 + 1)/1806 =
  (21*43 + 14*43 + 6*43 + 43)/(42*43) = (21 + 14 + 6 + 1)/42 = 1;
with a(5) = 47058 (not oblong number), we have
  1/2 + 1/3 + 1/11 + 1/23 + 1/31 + 1/47058 =
  (23529 + 15686 + 4278 + 2046 + 1518 + 1)/47058 = 1.
For n = 1 to 8, a(n) has n prime factors:
  a(1) = 2
  a(2) = 2 * 3
  a(3) = 2 * 3 *  7
  a(4) = 2 * 3 *  7 * 43
  a(5) = 2 * 3 * 11 * 23 *  31
  a(6) = 2 * 3 * 11 * 23 *  31 * 47059
  a(7) = 2 * 3 * 11 * 17 * 101 *   149 *       3109
  a(8) = 2 * 3 * 11 * 23 *  31 * 47059 * 2217342227 * 1729101023519
If a(n)+1 is prime, then a(n)*[a(n)+1] is also primary pseudoperfect. We have the chains: a(1) -> a(2) -> a(3) -> a(4); a(5) -> a(6). (End)
A primary pseudoperfect number (greater than 2) is oblong if and only if it is not the initial member of a chain. - _Daniel Forgues_, May 29 2013
If a(n)-1 is prime, then a(n)*(a(n)-1) is a Giuga number (A007850). This occurs for a(2), a(3), and a(5). See A235139 and the link "The p-adic order . . .", Theorem 8 and Example 1. - _Jonathan Sondow_, Jan 06 2014

M. A. Alekseyev, J. M. Grau, A. M. Oller-Marcen. Computing solutions to the congruence 1^n + 2^n + ... + n^n == p (mod n). Discrete Applied Mathematics, 2018. doi:10.1016/j.dam.2018.05.022 arXiv:1602.02407 [math.NT]
W. Butske, L. M. Jaje, and D. R. Mayernik, On the Equation Sum_{p|N} 1/p + 1/N = 1, Pseudoperfect numbers and partially weighted graphs, Math. Comput., 69 (1999), 407-420. [Title corrected by _Jonathan Sondow_, Apr 11 2012]
J. M. Grau, A. M. Oller-Marcen, and J. Sondow, On the congruence 1^m + 2^m + ... + m^m == n (mod m) with n|m, arXiv:1309.7941 [math.NT], 2013.
J. M. Grau, A. M. Oller-Marcén, and D. Sadornil, On µ-Sondow Numbers, arXiv:2111.14211 [math.NT], 2021.
John Machacek, Egyptian Fractions and Prime Power Divisors, arXiv:1706.01008 [math.NT], 2017.
J. Sondow and K. MacMillan, Reducing the Erdos-Moser equation 1^n + 2^n + . . . + k^n = (k+1)^n modulo k and k^2, Integers 11 (2011), #A34.
J. Sondow and K. MacMillan, Primary pseudoperfect numbers, arithmetic progressions, and the Erdos-Moser equation, Amer. Math. Monthly, 124 (2017) 232-240; arXiv:math/1812.06566 [math.NT], 2018.
J. Sondow and E. Tsukerman, The p-adic order of power sums, the Erdos-Moser equation, and Bernoulli numbers, arXiv:1401.0322 [math.NT], 2014; see section 4.
Eric Weisstein's World of Mathematics, Primary pseudoperfect number.
Wikipedia, Primary pseudoperfect number.
OEIS Wiki, Primary pseudoperfect numbers.

Cf. A005835, A007850, A069359, A168036, A190272, A191975, A203618, A216825, A216826, A230311, A235137, A235138, A235139, A236433.

pQ[n_] := (f = FactorInteger[n]; 1/n + Sum[1/f[[i]][[1]], {i, Length[f]}] == 1)
Select[Range[2, 10^6], pQ[#] &] (* Robert Price, Mar 14 2020 *)

isok(n) = if (n > 1, my(f=factor(n)[,1]); 1/n + sum(k=1, #f, 1/f[k]) == 1); \\ Michel Marcus, Oct 05 2017

from sympy import primefactors
A054377 = [n for n in range(2,10**5) if sum([n/p for p in primefactors(n)]) +1 == n] # Chai Wah Wu, Aug 20 2014

A031971(a(n)) (mod a(n)) = A233045(n). - Jonathan Sondow, Dec 11 2013
A069359(a(n)) = a(n) - 1. - Jonathan Sondow, Apr 16 2014
a(n) == 36*(n-2) + 6 (mod 288) for n = 2,3,..,8. - Kieren MacMillan and Jonathan Sondow, Sep 20 2017

A235137 a(n) = Sum_{k = 1..n} k^phi(n), where phi(n) = A000010(n).

Original entry on oeis.org

1, 3, 14, 30, 979, 91, 184820, 8772, 978405, 25333, 40851766526, 60710, 36720042483591, 19092295, 5666482312, 9961449608, 76762718946972480009, 105409929, 164309788542828686799730, 70540730666, 15909231318568907, 67403375450475, 1433191209985108404653810959324, 351625763020, 15975648280734359596251725645

Offset: 1

Jonathan Sondow and Emmanuel Tsukerman, Jan 03 2014

nonn

a(n) == -1 (mod n) if and only if n is prime or is a Giuga number A007850.

a(n) == 1 (mod n) if (and probably only if) n is a primary pseudoperfect number A054377.

			a(4) = 30 since 1^(phi(4)) + 2^(phi(4)) + 3^(phi(4)) + 4^(phi(4))= 1^2 + 2^2 + 3^2 + 4^2 = 1 + 4 + 9 + 16 = 30.
a(5) = 979, since phi(5) = 4 and 1^4 + 2^4 + 3^4 + 4^4 + 5^4 = 1 + 16 + 81 + 256 + 625 = 979.
a(6) = 91, since phi(6) = 2 and 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2 = 1 + 4 + 9 + 16 + 25 + 36 = 91.

Seiichi Manyama, Table of n, a(n) for n = 1..388
J. Sondow and K. MacMillan, Reducing the Erdős-Moser equation 1^n + 2^n + ... + k^n = (k+1)^n modulo k and k^2, Integers 11 (2011), #A34.
J. Sondow and E. Tsukerman, The p-adic order of power sums, the Erdos-Moser equation, and Bernoulli numbers, arXiv:1401.0322 [math.NT], 2014; see section 4.
Wikipedia, Giuga number
Wikipedia, Primary pseudoperfect number

Cf. A000010, A007850, A054377, A235138.

a[n_] := Sum[PowerMod[i, EulerPhi@n, n], {i, n}]

a(n) = sum(k=1, n , k^eulerphi(n)); \\ Michel Marcus, Oct 21 2015

a(n) (mod n) = A235138(n).

cp's OEIS Frontend

A007850 Giuga numbers: composite numbers n such that p divides n/p - 1 for every prime divisor p of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A054377 Primary pseudoperfect numbers: numbers n > 1 such that 1/n + sum 1/p = 1, where the sum is over the primes p | n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A235137 a(n) = Sum_{k = 1..n} k^phi(n), where phi(n) = A000010(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula