|
| |
|
|
A007850
|
|
Giuga numbers: composite numbers n such that p divides n/p - 1 for every prime divisor p of n.
|
|
52
|
|
|
|
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, 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
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 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
|
|
|
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.
J. M. Grau, A. M. Oller-Marcén, and D. Sadornil, On µ-Sondow Numbers, arXiv:2111.14211 [math.NT], 2021.
|
|
|
FORMULA
|
Sum_{i = 1..a(n)-1} i^phi(a(n)) == -1 (mod a(n)). - Jonathan Sondow, Jan 03 2014
|
|
|
EXAMPLE
|
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)
|
|
|
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
(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)))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice,hard,more
|
|
|
AUTHOR
|
D. Borwein, J. M. Borwein, P. B. Borwein and R. Girgensohn
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
