|
%I #167 Sep 07 2023 04:11:35
%S 30,858,1722,66198,2214408306,24423128562,432749205173838,
%T 14737133470010574,550843391309130318,244197000982499715087866346,
%U 554079914617070801288578559178,1910667181420507984555759916338506
%N Giuga numbers: composite numbers n such that p divides n/p - 1 for every prime divisor p of n.
%C 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
%C One further Giuga number is known with 10 prime factors, namely:
%C 420001794970774706203871150967065663240419575375163060922876441614\
%C 2557211582098432545190323474818 =
%C 2 * 3 * 11 * 23 * 31 * 47059 * 2217342227 * 1729101023519 * 8491659218261819498490029296021 * 58254480569119734123541298976556403 but this may not be the next term. (See the Butske et al. paper.)
%C 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
%C 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
%C 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
%C 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
%C The prime factors of a(n) are listed as n-th row of A236434. - _M. F. Hasler_, Jul 13 2015
%C 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
%C 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
%C A composite number n is a Giuga number if and only if A326690(n) = 1. - _Jonathan Sondow_, Jul 19 2019
%C 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
%C 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
%D J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 30, pp 11, Ellipses, Paris 2008.
%H 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:<a href="http://doi.org/10.1016/j.dam.2018.05.022">10.1016/j.dam.2018.05.022</a> arXiv:<a href="http://arxiv.org/abs/1602.02407">1602.02407</a> [math.NT], 2016.
%H D. Borwein, J. M. Borwein, P. B. Borwein and R. Girgensohn, <a href="http://www.jstor.org/stable/2975213">Giuga's Conjecture on Primality</a>, Amer. Math. Monthly 103, No. 1, 40-50 (1996).
%H J. M. Borwein and E. Wong, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.5509">A Survey of Results Relating to Giuga's Conjecture on Primality</a>, Vinet, Luc (ed.): Advances in Mathematical Sciences: CRM's 25 Years. Providence, RI: American Mathematical Society. CRM Proc. Lect. Notes. 11, 13-27 (1997).
%H William Butske, Lynda M. Jaje, and Daniel R. Mayernik, <a href="http://dx.doi.org/10.1090/S0025-5718-99-01088-1">On the equation Sum_{p | N} 1/p + (1/N)=1, pseudoperfect numbers and perfectly weighted graphs</a>, Math. Comp. 69 (2000), no. 229, 407-420.
%H José María Grau and Antonio M. Oller-Marcén, <a href="http://arxiv.org/abs/1103.2298">Giuga Numbers and the arithmetic derivative.</a>, arXiv:1103.2298 [math.NT], 2011; <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Oller/oller5.html">J. Int. Seq. 15 (2012) 12.4.1</a>
%H José María Grau and Antonio M. Oller-Marcén, <a href="http://arxiv.org/abs/1103.3483">Generalizing Giuga's conjecture</a>, arXiv:1103.3483 [math.NT], 2011.
%H J. M. Grau and A. M. Oller-Marcén, <a href="http://arxiv.org/abs/1311.3522">On the congruence sum_{j=1}^{n-1} j^{k(n-1)} == -1 (mod n); k-strong Giuga and k-Carmichael numbers</a>, arXiv preprint arXiv:1311.3522 [math.NT], 2013.
%H J. M. Grau, A. M. Oller-Marcén, and D. Sadornil, <a href="https://arxiv.org/abs/2111.14211">On µ-Sondow Numbers</a>, arXiv:2111.14211 [math.NT], 2021.
%H John Machacek, <a href="https://arxiv.org/abs/1706.01008">Egyptian Fractions and Prime Power Divisors</a>, arXiv:1706.01008 [math.NT], 2017.
%H Mersenne Forum, <a href="http://www.mersenneforum.org/showthread.php?t=4666">Giuga numbers</a>
%H Romeo Meštrović, <a href="http://arxiv.org/abs/1305.1867">Generalizations of Carmichael numbers I,</a> arXiv:1305.1867 [math.NT], May 04 2013.
%H R. Mestrovic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Mestrovic/mes4.html">On a Congruence Modulo n^3 Involving Two Consecutive Sums of Powers</a>, Journal of Integer Sequences, Vol. 17 (2014), 14.8.4.
%H J. Sondow and K. MacMillan, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.124.3.232">Primary pseudoperfect numbers, arithmetic progressions, and the Erdős-Moser equation</a>, Amer. Math. Monthly, 124 (2017) 232-240; <a href="http://arxiv.org/abs/1812.06566">arXiv:math/1812.06566 [math.NT]</a>, 2018.
%H J. Sondow and E. Tsukerman, <a href="https://arxiv.org/abs/1401.0322">The p-adic order of power sums, the Erdos-Moser equation, and Bernoulli numbers</a>, arXiv:1401.0322 [math.NT], 2014; see section 4.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GiugaNumber.html">Giuga Number.</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Agoh-Giuga_conjecture">Agoh-Giuga conjecture</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Giuga_number">Giuga number</a>
%F Sum_{i = 1..a(n)-1} i^phi(a(n)) == -1 (mod a(n)). - _Jonathan Sondow_, Jan 03 2014
%e From _M. F. Hasler_, Jul 13 2015: (Start)
%e 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.
%e 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.
%e (End)
%t fQ[n_] := AllTrue[First /@ FactorInteger@ n, Divisible[n/# - 1, #] &]; Select[Range@ 100000, CompositeQ@ # && fQ@ # &] (* _Michael De Vlieger_, Oct 05 2015 *)
%o (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
%o (Python)
%o from itertools import count, islice
%o from sympy import isprime, primefactors
%o def A007850_gen(startvalue=2): # generator of terms >= startvalue
%o return filter(lambda x: not isprime(x) and all((x//p-1) % p == 0 for p in primefactors(x)), count(max(startvalue,2)))
%o A007850_list = list(islice(A007850_gen(),4)) # _Chai Wah Wu_, Feb 19 2022
%Y Cf. A054377, A216823, A216824, A235137, A235138, A235140, A235363, A236434, A326690.
%K nonn,nice,hard,more
%O 1,1
%A D. Borwein, J. M. Borwein, P. B. Borwein and R. Girgensohn
%E a(12) from _Fred Schneider_, Jul 04 2006
%E Further references from _Fred Schneider_, Aug 19 2006
%E Definition corrected by _Jonathan Sondow_, Sep 16 2012
| 