Finding Cousins of Giuga Numbers: Can You Solve This Prime Number Puzzle?

[kbannister]

Homework Statement

Find first 10 6-th cousins of the Giuga Numbers

Relevant Equations

kernel = sum(1./P)-1/X, a MATLAB expression where sum(1./P) = sum of the reciprocals
of the prime factors of a composite number having ONLY prime factors, e.g., 14, 21, or 55388487,
and X = the product of those prime factors, e.g., 3*7*11*347*691 = 55388487. In this latter
case, the RHS turns out to be = 4/7.

A Giuga Number is a positive integer x > 1 with prime factors p1,p2,p3,...pi
that satifies the relationship 1/p1 + 1/p2 + 1/p3 +...+ 1/pi - 1/x = k, where k is a
positive integer, k=1 in this case.

The first few Giuga numbers are 30, 858, 1772, and 66,198. For example, for x = 30 the prime factors are 2, 3, 5, so that we have
1/2 + 1/3 + 1/5 - 1/30 = 31/30 - 1/30 = 1 = k.

The problem now is to find "Cousins" of the Giuga numbers, namely the
first 10 unique combinations of primes, and their reciprocals, such
that a modified RHS, namely, k/(n+1), where n = 6, and 1 <= k an integer <= n, is
satisfied? For example, RHS values of 1/7, 2/7, 3/7, 4/7, 5/7, and 6/7 are OK.

By brute force looping in MATLAB, I have found the first 8 such numbers,
but #9 and #10 so far have eluded me. Also, 7 always appears as a factor. I believe the higher numbers might be very large - similar in behavior to the higher Giuga numbers.

I thought one way to speed up finding them is to simply use different "strides" in my
MATLAB loop, e.g., instead of 1, use 2*7, 3*7, 2*3*7, etc. I don't know, perhaps
there are cleverer ways based on more advanced knowledge about prime
number theory knowledge than I possess. I am an engineer, not a mathematician,
so prime number theory is not part of my kitbag of tools.

More about on Giuga numbers may be found in the on-line Encyclopedia
of Integer Sequences article: "Giuga numbers." The link is: https://oeis.org/A007850

 

[fresh_42]

You said it yourself. You probably ran out of digits or precision.

Why do you want to find those numbers?

 

[kbannister]

Thank you for your comments. To the contrary, MATLAB can handle the number of digits, as well as the
precision, comprising the numbers sought OK; the challenge is to find those digits expeditiously.

 

[fresh_42]

Thank you for your comments. To the contrary, MATLAB can handle the number of digits, as well as the
precision, comprising the numbers sought OK; the challenge is to find those digits expeditiously.

I'm still not sure which numbers you want to find. There are only 12 known Giuga numbers. Not the definition but an equivalent description is a square-free (all prime factors are different) composite number (not a prime itself) $n$ such that
$$
\sum_{p|n} \dfrac{1}{p}-\prod_{p|n}\dfrac{1}{p}=\sum_{p|n} \dfrac{1}{p}-\dfrac{1}{n} =: k \in \mathbb{N}
$$
And $k=1$ for all known examples.

If I understood you correctly, then you are looking for numbers $n=p_1\cdots p_m$ with pairwise different primes $p_i$ such that
$$
\sum_{p|n} \dfrac{1}{p}-\prod_{p|n}\dfrac{1}{p}=\sum_{p|n} \dfrac{1}{p}-\dfrac{1}{n} = \dfrac{k}{n+1}
$$
for some natural number $1\leq k \leq n.$

Hence you can use any efficient algorithm that produces Giuga numbers and instead of checking for $k=1$ or $k\in \mathbb{N}$ you have place an outer loop over all $k$ and check for $\dfrac{k}{n+1}.$

Is your list of primes long enough? The largest Giuga number has a pretty high prime:
2×3×7×43×1831×138683×2861051×1456230512169437

The question remains: why?

 

[fresh_42]

If you want to look for something interesting then show:

No natural number $n$ is simultaneously Giuga and Carmichael number.

Both are square-free and composite, and have the following additional property:
\begin{align*}
p\,|\,n &\Longrightarrow p\,|\,\left(\dfrac{n}{p}-1\right) \quad \text{Giuga}\\
p\,|\,n &\Longrightarrow (p-1)\,|\,\left(\dfrac{n}{p}-1\right) \quad \text{Carmichael}
\end{align*}

 

[kbannister]

Why? I suppose the same question could be asked of any number theory inquiry, or for that matter,
and attempt to climb an unscaled mountain. "Because it's there!" It is interesting that nowhere in my
collection of number theory books are Giuga Numbers mentioned.

I should mention that in my MATLAB code, I extract the prime factors of each trial number N using the MATLAB "factor" command (call that list of factors Nfact). Then I get Nfact's length (lengthN) using the "size" command.

Then I use the MATLAB "unique" and "size" commands to get the unique factors (uniqueN), and the length of uniqueN (ulengthN). If lengthN = ulengthN, then I know I have a candidate which has only unique prime factors (i.e., no duplicates), and so is OK for "cousin testing." I suppose if N is a prime itself, I waste a cycle.

It could very well be the case that your approach above is more efficient, but unfortunately, I don't know how to program it.

 

[fresh_42]

Yes. It looks like an exponential algorithm. You have to check all possible subsets of a set of primes, depending on how far you want to go:
Given a list of primes $\{p_1,\ldots,p_n\}$ select for $k=2$ to $n$ all subsets of length $k$ and check the equation.

The actual definition that I gave in post #5 should be significantly faster, but that doesn't fit your modified RHS. One had to look at the proof that both definitions are equivalent and see what you get with a fraction on the RHS instead.

At least you know that every prime factor occurs only once.

 

[berkeman]

Why? I suppose the same question could be asked of any number theory inquiry, or for that matter,
and attempt to climb an unscaled mountain. "Because it's there!" It is interesting that nowhere in my
collection of number theory books are Giuga Numbers mentioned.

So you would like to solve fundamental mathematical problems using MATLAB? Sorry if I'm misunderstanding your motives...

 

[fresh_42]

So you would like to solve fundamental mathematical problems using MATLAB? Sorry if I'm misunderstanding your motives...

Not so much fundamental as artificial. Number theory has many conjectures that are unproven. They definitely need no fractions where formerly were integers.

 

[kbannister]

Thank you for your response. From what I can tell - and G. H. Hardy's classic work "An Introduction to the Theory of Numbers" echoes your sentiment - there are many conjectures about the primes that are so easy to state, yet so hard to prove. I don't think my "Cousin" problem is any more than some variation on a brute force search. I agree there are many tools available to work with primes and do the messy calculations. MATLAB just happens to be a platform I have some limited familiarity with. I suppose one could tackle the problem using clever C or Python programming- or even symbolic algebra packages such as Mathematica or Waterloo Maple, but I don't have the financial resources for the latter.

 

[fresh_42]

Keep in mind that a program isn't a proof of something. At least in general. You can use programs to check specific configurations as it has been done with the 4 color problem, or use it to find numbers with specific properties. I guess this has been done to find the known dozen Giuga numbers.

They have checked the Riemann hypothesis for incredibly many numbers and haven't found a counterexample. However, this doesn't prove anything.

 

[kbannister]

Thank you. You are "preaching to the choir." In engineering we're often happy if we get within 10% of the answer, LOL. I remember when I reported to work at a Navy lab (which no longer exists) in 1976, one of my colleagues had just returned from a mathematics conference where they announced the 4-color map problem had just been "solved."

Be that as it may, I continue to search for Giuga Cousins #9 and 10.

 

[fresh_42]

Be that as it may, I continue to search for Giuga Cousins #9 and 10.

I'm still not sure what you mean by Giuga's cousins. Let me explain. I read it as a search for natural numbers $n=p_1\cdots p_m$ such that $\dfrac{1}{p_1}+\ldots+\dfrac{1}{p_m}-\dfrac{1}{n}=\dfrac{k}{n+1}$ for some integer $1\leq k\leq n$.

If this is correct, then multiplication by $n$ yields
$$
\dfrac{n}{p_1}+\ldots+\dfrac{n}{p_m}-1=\dfrac{k\cdot n}{n+1}
$$
where the LHS is a positive integer, say $z_0$. Then
\begin{align*}
k\cdot n =(n+1)\cdot z_0 &\Longrightarrow z_0=(k-z_0)\cdot n \\
&\Longrightarrow z_1:=\dfrac{z_0}{n}=k-z_0\in \mathbb{N}\\
&\Longrightarrow 2 \leq z_1+z_0 = k \leq n\\
&\Longrightarrow 2\leq \min\{z_0\, , \,z_1\} \leq \dfrac{n+1}{2}
\end{align*}
Case 1:
$z_0=\min\{z_0\, , \,z_1\}=\dfrac{kn}{n+1}\leq \dfrac{n+1}{2}$ and so $k\leq \dfrac{(n+1)^2}{2n}=\dfrac{n}{2}+1+\dfrac{1}{2n},$ and since $k$ is an integer, $k\leq \dfrac{n}{2}+1.$ This saves you about half of your computation time.

Case 2:
$z_1=\min\{z_0\, , \,z_1\}\leq \dfrac{n+1}{2}$
\begin{align*}
2\leq z_1&=\dfrac{z_0}{n}=k-z_0=k-\dfrac{kn}{n+1}=\dfrac{k}{n+1}\leq \dfrac{n+1}{2}\\
\Longrightarrow \quad 4(n+1)&\leq 2k \leq \min\{(n+1)^2\, , \,2n\}=2n
\end{align*}
This is impossible.

So $z_0\leq z_1 \Longleftrightarrow \dfrac{kn}{n+1}\leq \dfrac{k}{n+1} \Longleftrightarrow n\leq 1$ which is again impossible.

This results in three possibilities:

• I didn't understand you correctly.
• I have made a mistake.
• There are no Giuga cousins.

 

[kbannister]

Thanks very much. About to watch the Buc-Rams football game, and I have only skimmed your message, but FYI, I have attached an Excel spread sheet of the "cousins" I have found so far, using brute force searching with MATLAB. I will take a look at your suggestions to see what can be done.

 

[fresh_42]

About to watch the Buc-Rams

Whose side you're on? I think the second game will be the better one. Nevertheless, it can't be as bad as yesterday.

 

[kbannister]

We're rooting for the Bucs, given we are in Boston, MA now, and followed Tom Brady's successes here with the Pats. But those Rams look very healthy and good, so IDK how well Brady will be able to do with so many players knocked out. I hate post-season games where it's a blow-out.

 

[fresh_42]

I made one of those Facebook quizzes where the result was which team I should support. The outcome was the Pats. Well, as a European, I'm not determined to one specific franchise. I like Mahomes's craziness. Let's see. Have fun!

 

[kbannister]

I wish it were so simple. OK, I took a look at your equations a few messages ago and need to point out that the "-1/n" term should be "-1/X," where big X is the product of the primes p1,p2,p3,...pm, and over to the left side where you have "n = p1p2p3...pm" it should read "X = the product of the primes p1,p2,p3,...pm." So, in the Excel table I attached earlier, the column with values 14, 21, 182, 1463, and so on, are the "big X" values I have been seeking. For 14, we have p1 = 2, p2 = 7, so X = 2*7 = 14. Then we have
1/2 + 1/7 - 1/X = 1/2 + 1/7 - 1/14
7/14 + 2/14 - 1/14 = 9/14-1/14 = 8/14 = 4/7, so k=4, which is OK
because 1=< k =< 6, for n = 6 and we can go home, turn on the tube,
and have a Coke!

 

[fresh_42]

So you are looking for an $x=p_1\cdots p_m$ such that
$$
0<\dfrac{1}{p_1}+\ldots+\dfrac{1}{p_m}-\dfrac{1}{x}=\dfrac{k}{n+1} <1
$$
for some numbers $k$ and $n$? So $15$ is also a solution, namely for $k=7$ and $n=14$. That doesn't make sense.

 

[kbannister]

Sir: Hooray for the Kansas City Chiefs! Not the result I'd hoped for, but WOW, what a game!

Thanking you once more for your patience. I need to say that n = 6, representing the "6th Giuga cousin."
So, the RHS becomes k/(n+1) = k/(6+1) = k/7. This means that when we do find an X, who with its prime
factors satisfies the inequality, the RHS can be any of 1/7, 2/7, ... 6/7, or k can be any of 1,2,3...6.

Looking at the sum 1/p1 + 1/p2 + ... + 1/pm, this looks like resistors in parallel. We know that the denominator
will end up being X, and the numerator will be some complicated algebraic expression. I wonder if this
yields any clues? For each k-value in turn, 1, 2, 3, ...6, we would get a different algebraic equation to be solved. Perhaps this knowledge could be used to speed up the search somehow?

When time allows, I may try looking for other nth cousins, such as 2nd, 3rd, and so on.

 

[fresh_42]

 

[pbuk]

Thanks very much. About to watch the Buc-Rams football game, and I have only skimmed your message, but FYI, I have attached an Excel spread sheet of the "cousins" I have found so far, using brute force searching with MATLAB. I will take a look at your suggestions to see what can be done.

That spreadsheet is dreadful - many of the numbers are actually entered as text which makes it very difficult to use.

Anyway you need to stop using Matlab for this, it is not the kind of thing it is good at floating point arithmetic for this, you need to convert your test to use integers as explained in the excellent answer to the thread you opened on MathWorks. As a consequence you have missed two results which satisfy your definition (if I have understood it correctly): the first of these is 1,722 = 2 x 3 x 7 x 41. I will not post the second one for a number of reasons, but I can tell you that it is less than 25,000,000.

Learn how to program, probably first in Python because it is easy and quite sufficient for this (although I actually used JavaScript: it found all the 10 solutions less than $6 \times10^7$ in about 4s).

 

[kbannister]

Thank you for your insightful comments. Sorry about the Excel spreadsheet. It turns out that 1722 is indeed one of the regular Giuga numbers, but not a 6th cousin. I actually let MATLAB cycle with a stride of 1 through and found the first eight 6th cousin values listed in my table. I have independently verified those values. The goal is to find the 9th and 10th values, which may likely be > 25,000,000. I surmise they may be in the billions somewhere.

Thanks so much for the tip about computer languages. I used to program in Python, probably back when you were in grade school, but have forgotten the details. I did not have a copy of it when I started work on this problem, but have since downloaded a version of it and bought a revised and updated copy of the "Python Bible." I don't know Javascript. I have known about Java and that it has many "children," and I have books about it, but I haven't used it. Oh and by the way, I also programmed in FORTRAN IV and BASIC, probably when your grandparents were teenagers in bellbottom trousers listening to the Beatles & Stones. What I like about MATLAB is that in pretty short order one can be calculating numbers & plotting things. There is also a huge expert MATLAB community out there one can consult with. Computer algebra packages such as Mathematica and Waterloo Maple also may offer powerful assists - if one can afford the subscription cost!

Just a word about "programming": My view is there are 100s, if not 1000s of wonderful programming languages, and they are all well and good. But without underlying mathematical theory - and algorithms - such as people like Don Knuth addressed in his classic works - seems to me you're sailing without a compass.

 

[Mark44]

I also programmed in FORTRAN IV and BASIC, probably when your grandparents were teenagers in bellbottom trousers listening to the Beatles & Stones.

I didn't write any code in FORTRAN IV, but I did write a fair amount of FORTRAN 77 and Fortran 95 code, as well as BASIC in a variety of flavors, and Pascal, Modula-2, C, C++, C#, Lisp, Java, JavaScript, Python, x-86 assembly, M68000 assembly, MIPS assembly, and ARMv7 assembly.

I was one of those people listening to the Beatles and the Stones, and even attended a Stones concert on their first tour in the US.

 

[pbuk]

It turns out that 1722 is indeed one of the regular Giuga numbers, but not a 6th cousin.

Check it. As was pointed out above you are running into problems with numerical precision, you need to multiply every term on both sides by $x$ so that you are working with integers:

$\frac{1722}{2} +\frac{1722}{3} + \frac{1722}{7} + \frac{1722}{41} - 1 = 861 + 574 + 246 + 42 - 1 = 1722 = 1722 \frac{k}{6 + 1}, k = 7$

or eqivalently work with exact fractions:

$\frac{1}{2} +\frac{1}{3} + \frac{1}{7} + \frac{1}{41} - \frac{1}{1722} = \frac{861 + 574 + 246 + 42 - 1}{1722} = 1 = \frac{k}{6 + 1}, k = 7$

I actually let MATLAB cycle with a stride of 1 through and found the first eight 6th cousin values listed in my table. I have independently verified those values.

But as has already been stated, your test is using floating point arithmetic for these computations which means that it misses some values due to roundoff error.

Thanks so much for the tip about computer languages. I used to program in Python, probably back when you were in grade school

I don't think so: Python first appeared 10 years after I left grade school.

I don't know Javascript. I have known about Java and that it has many "children," and I have books about it, but I haven't used it.

JavaScript has nothing to do with Java.

Oh and by the way, I also programmed in FORTRAN IV and BASIC, probably when your grandparents were teenagers in bellbottom trousers listening to the Beatles & Stones.

My grandparents were teenagers during the First World War. One was born in the 19th century.

But without underlying mathematical theory - and algorithms - such as people like Don Knuth addressed in his classic works - seems to me you're sailing without a compass.

Absolutely. And the most fundamental of all theory is an understanding of floating point arithmetic.

 

[pbuk]

The goal is to find the 9th and 10th values, which may likely be > 25,000,000. I surmise they may be in the billions somewhere.

You already have the 9th and 10th, it is the 5th (1,722) and 8th you are missing. The 11th is
1,925,224,630 $= \Pi ( 2, 5, 7, 101, 307, 887 ), k = 6$.

 

[kbannister]

For n = 6, k has to be .GE. 1 and .LE. to 6. Hence, the moniker "6th cousin."

Let's look at "6th cousin" #1, namely 14, which yields a RHS of 4/7, so k = 4 which satisfies 1 =< k =< 6.
OK, so - at least as it was in the old days - 14 has the prime factors 2 and 7, so
1/2+1/7-1/14 = 7/14 + 2/14 - 1/14 = 9/14 - 1/14 = 8/14, which upon simplification gives 4/7.
I mean no disrespect, sir, but without loss of generality, we can do this for 21, 182, 1463, 14098, 18802, 40305333, and 55388497.
That takes us up to cousin #8. Now the challenge is find cousins #9 and #10.

 

[Mark44]

My grandparents were teenagers during the First World War. One was born in the 19th century.

I remember only my two grandmothers, one of whom was born in 1885. So she was 30 not long after the start of WW I.

Absolutely. And the most fundamental of all theory is an understanding of floating point arithmetic.

This...

 

[pbuk]

When you have made incorrect assumptions about a person it is conventional to start with an apology*, however...

For n = 6, k has to be .GE. 1 and .LE. to 6.

I missed this condition from your first post. It would have helped if you had restated it in your post #23.

Hence, the moniker "6th cousin."

Do you have any tone of communication that is not condescending? I had inferred that 6th cousin referred to the condition $n = 6$.

OK, so - at least as it was in the old days - 14 has the prime factors 2 and 7, so

There you go again with the condescension; do you not see how foolish this sounds?

1/2+1/7-1/14 = 7/14 + 2/14 - 1/14 = 9/14 - 1/14 = 8/14, which upon simplification gives 4/7. I mean no disrespect, sir, but without loss of generality, we can do this for 21, 182, 1463, 14098, 18802, 40305333, and 55388497.
That takes us up to cousin #8. Now the challenge is find cousins #9 and #10.

Nope, you have still missed one (the 6th) < 25,000,000 with k = 6. Its greatest prime factor is much larger than for the other solutions, more than 4,900, which is probably why it is lost in the roundoff error of double precision arithmetic. If you want to find it then, I repeat, you need to use the modified version of your equation that uses only integers (no extended range arithmetic is required: the 53 bit integers of IEEE 754 double precision are plenty for candidates up to about $10^{11}$).

I have already given you the 10th.

* It is particularly inappropriate to make assumptions about a persons family: fortunately all my grandparents were alive during the 60's and 70's; if this were not the case your assertion that they were 'dancing to the Stones' would have been distressing rather than simply foolish.

 

[kbannister]

MATLAB does have a nifty symbolic toolbox, so one can use it to add a series of fractions symbolically and
get the result as a ratio of integers. That's what I used to verify my first 8 "cousins", not "floating point arithmetic." I suppose one schooled in computer algebra (not my forte) could compare, contrast, and criticize how Mathworks has implemented their symbolic toolbox vice how Wolfram and Maple have done theirs

I have found the #9 6th Giuga cousin. It is 1,925,224,630, and its factors are 2 5 7 101 307 887,
resulting in a RHS of 6/7.

 

[Mark44]

or eqivalently work with exact fractions: $\frac{1}{2} +\frac{1}{3} + \frac{1}{7} + \frac{1}{41} - \frac{1}{1722} = \frac{861 + 574 + 246 + 42 - 1}{1722} = 1 = \frac{k}{6 + 1}, k = 7$

Both points made by @pbuk are very important.
As an example, I wrote a Python program to calculate 1 + 1/2 + 1/3 + ... + 1/n. This isn't the same as the calculation done in this thread, but it shows the effects of error accumulation for different calculation algorithms.

Ex. 1 - Calculate 1 + 1/2 + 1/3 + ... + 1/15
By writing the above as a single fraction over a common denominator of 15! the result was 3.3182289932289932
By brute force addition of the fractions the result was 3.3182289932289937
The difference between the two results is about $4.5 \times 10^{-16}$.

Ex. 2 - Calculate 1 + 1/2 + 1/3 + ... + 1/20
Same results from both methods

Ex. 3 - Calculate 1 + 1/2 + 1/3 + ... + 1/50
By writing the above as a single fraction over a common denominator of 30! the result was 4.499205338329425
My brute force addition of the fractions the result was 4.499205338329423
The difference between these two results is about $1.8 \times 10^{-15}$

 

[pbuk]

That's what I used to verify my first 8 "cousins", not "floating point arithmetic."

But you did not use that to eliminate any candidates, you used floating point arithmetic which resulted in you missing 24,695,930 = product(2, 5, 7, 71, 4969), k = 6.

I have found the #9 6th Giuga cousin. It is 1,925,224,630, and its factors are 2 5 7 101 307 887,
resulting in a RHS of 6/7.

I posted this solution in #26.

 

[kbannister]

But you did not use that to eliminate any candidates, you used floating point arithmetic which resulted in you missing

When you have made incorrect assumptions about a person it is conventional to start with an apology*, however...I missed this condition from your first post. It would have helped if you had restated it in your post #23.Do you have any tone of communication that is not condescending? I had inferred that 6th cousin referred to the condition $n = 6$.There you go again with the condescension; do you not see how foolish this sounds?Nope, you have still missed one (the 6th) < 25,000,000 with k = 6. Its greatest prime factor is much larger than for the other solutions, more than 4,900, which is probably why it is lost in the roundoff error of double precision arithmetic. If you want to find it then, I repeat, you need to use the modified version of your equation that uses only integers (no extended range arithmetic is required: the 53 bit integers of IEEE 754 double precision are plenty for candidates up to about $10^{11}$).

I have already given you the 10th.

* It is particularly inappropriate to make assumptions about a persons family: fortunately all my grandparents were alive during the 60's and 70's; if this were not the case your assertion that they were 'dancing to the Stones' would have been distressing rather than simply foolish.

I posted this solution in #26.

Excellent PbuK! I did miss that one - either I did not go far enough to find 4969, or did not use close enough tolerances. I did revise my algorithm to use loops based on only prime factors (although even there I did not go up to a factor as high as 4969).

I think this put the problem to rest.