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

Author

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

Keywords

• nonn
• nice
• hard
• more

Comments

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

Examples

			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)
		

References

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

Links

• 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

Crossrefs

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

Programs

Mathematica

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

PARI

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

Python

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

Formula

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

Extensions

a(12) from Fred Schneider, Jul 04 2006

Further references from Fred Schneider, Aug 19 2006

Definition corrected by Jonathan Sondow, Sep 16 2012