

A007850


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


31



30, 858, 1722, 66198, 2214408306, 24423128562, 432749205173838, 14737133470010574, 550843391309130318, 244197000982499715087866346, 554079914617070801288578559178, 1910667181420507984555759916338506
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


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, being n' 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..n1} 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 pn} 1/p = 1/n + an integer. (In fact, all known Giuga numbers n satisfy Sum_{prime pn} 1/p = 1/n + 1.)  Jonathan Sondow, Jan 08 2014
The prime factors of a(n) are listed as nth 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..n1} k^lambda(n) == 1 (mod n), where lambda(n) = A002322(n).  Thomas Ordowski and Giovanni Resta, Jul 25 2018


REFERENCES

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


LINKS

Table of n, a(n) for n=1..12.
M. A. Alekseyev, J. M. Grau, A. M. OllerMarcen. 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]
D. Borwein, J. M. Borwein, P. B. Borwein and R. Girgensohn, Giuga's Conjecture on Primality, Amer. Math. Monthly 103, No. 1, 4050 (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, 1327 (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, 407420.
José María Grau and Antonio M. OllerMarcé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. OllerMarcén, Generalizing Giuga's conjecture, arXiv:1103.3483 [math.NT], 2011.
J. M. Grau and A. M. OllerMarcén, On the congruence sum_{j=1}^{n1} j^{k(n1)} == 1 (mod n); kstrong Giuga and kCarmichael numbers, arXiv preprint arXiv:1311.3522 [math.NT], 2013.
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 ErdosMoser equation, Amer. Math. Monthly, 124 (2017) 232240; arXiv:math/1812.06566 [math.NT], 2018.
J. Sondow and E. Tsukerman, The padic order of power sums, the ErdosMoser equation, and Bernoulli numbers, arXiv:1401.0322 [math.NT], 2014; see section 4.
Eric Weisstein's World of Mathematics, Giuga Number.
Wikipedia, AgohGiuga conjecture
Wikipedia, Giuga number


FORMULA

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


EXAMPLE

From M. F. Hasler, Jul 13 2015: (Start)
The prime divisors of 30 are {2, 3, 5}, and 2 divides 30/21 = 14, 3 divides 30/31 = 9, and 5 divides 30/51 = 5.
The prime divisors of 858 are {2, 3, 11, 13} and 858/21 = 428 is even, 858/31 = 285 is divisible by 3, 858/111 = 77 is a multiple of 11, and 858/131 = 65 = 13*5.
(End)


MATHEMATICA

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


PROG

(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


CROSSREFS

Cf. A054377, A216823, A216824, A235137, A235138, A235140, A235363, A236434.
Sequence in context: A143169 A256324 A001201 * A162833 A163208 A163552
Adjacent sequences: A007847 A007848 A007849 * A007851 A007852 A007853


KEYWORD

nonn,nice,hard,more


AUTHOR

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


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


STATUS

approved



