Is it a Giuga number?

Question

Giuga numbers (A007850) are composite numbers \$n\$ such that, for each prime factor \$p_i\$ of \$n\$, \$p_i \mid \left( \frac n {p_i} -1 \right)\$. That is, that for each prime factor \$p_i\$, you can divide \$n\$ by the factor, decrement it and the result is divisible by \$p_i\$

For example, \$n = 30\$ is a Giuga number. The prime factors of \30ドル\$ are \2,ドル 3, 5\$:

• \$\frac {30} 2 - 1 = 14\$, which is divisible by \2ドル\$
• \$\frac {30} 3 - 1 = 9\$, which is divisible by \3ドル\$
• \$\frac {30} 5 - 1 = 5\$, which is divisible by \5ドル\$

However, \$n = 66\$ isn't, as \$\frac {66} {11} - 1 = 5\$ which is not divisible by \11ドル\$.

The first few Giuga numbers are \30,ドル 858, 1722, 66198, 2214408306, ...\$

---

Given a positive integer \$n\$, determine if it is a Giuga number. You can output either:

• Two distinct, consistent values to indicate whether \$n\$ is a Giuga number or not (e.g True/False, 1/0, 5/"abc")
• Two classes of values, which are naturally interpreted as truthy and falsey values in your language (e.g. 0 and non-zero integers, and empty vs non-empty list etc.)

Additionally, you may choose to take a black box function \$f(x)\$ which returns 2 distinct consistent values that indicate if its input \$x\$ is prime or not. Again, you may choose these two values.

This is code-golf, so the shortest code in bytes wins.

---

Test cases

 1 -> 0
 29 -> 0
 30 -> 1
 66 -> 0
 532 -> 0
 858 -> 1
1722 -> 1
4271 -> 0

• caird coinheringaahing: Brownie points for beating or tying my 9 byte Jelly answer (outputs 1/0)
• theorist: The oeis page already contains a 58-byte Mathematica solution by Michael De Vlieger: f[n_]:=AllTrue[First/@FactorInteger@n,Divisible[n/#-1,#]&]. It can be shortened to 48 bytes as follows, but I'm not sure if it's different enough from De Vlieger's code to justify posting as an answer: AllTrue[First/@FactorInteger@#,n|->n∣(#/n-1)]&

Answer 1

Jelly, 8 bytes

Æfḟɓ÷’ọȦ

Try it online!

This version is mostly caird's, and I merged one of my golfs into it. Posted with their permission.

Æfḟɓ÷’ọȦ Main Link
Æf Take the prime factors
 ḟ And filter out the original (if x is prime, this list is empty, otherwise, nothing changes)
 ɓ---- Call this chain dyadically with reversed arguments: x on the left, factors on the right
 ÷ Divide x by each factor
 ’ Decrement each quotient
 ọ Count divisibility of each result by the corresponding factor
 Ȧ Are any and all truthy? That is, the list is all truthy and is not empty

This was my original solution:

Jelly, 9 bytes

:’ọɗÆfȦ>Ẓ

Try it online!

Gives 1 for Guiga numbers and 0 otherwise.

:’ọɗÆfȦ>Ẓ Main Link (monadic)
---ɗ Last three links as a dyad
 Æf Monad - get array of prime factors
:’ọ Since this is a 2,1-chain, this dyadic section is called with `x` on the left and the prime factors on the right
: - divide x by each prime factor
 ’ - decrement each
 ọ - how many times is each result divisible by its matching prime factor?
 Ȧ Check if all are true
 >Ẓ 2,1-chain: check if that result is greater than whether or not x is prime (in other words, true if and only the above check was true and it is not a prime)

• Unrelated String: Worth noting that :ÆfS’= seems to work but its actual validity is unknown, as per the Wikipedia article. (Having a hard time taking the 1 out of :ÆfS’ọ@.)

Answer 2

Zsh -eo extendedglob 36 bytes

>`factor 1ドル`
for x (<->~1ドル)$[1ドル/x%x]

Attempt This Online!

Outputs via exit code: zero for Giuga numbers and non-zero otherwise.

This makes heavy abuse of the rule

Additionally, you may choose to take a black box function f(x) which returns 2 distinct consistent values that indicate if its input x is prime or not. Again, you may choose these two values.

The function is assumed to:

• be predefined under the name 1
• output either 0 or 1 to standard out, for prime and non-prime respectively
• always succeed (exit with a status code of 0)

For each prime factor x, $[1ドル/x%x] takes the residue of the input mod x and tries to execute it as a command. The only number that's defined as a command is the black-box function 1, which will succeed; otherwise, the command fails, and because of the -e option, Zsh exits with a non-zero status code.

---

If this is cheating, have this:

Zsh, 40 bytes

>`factor 1ドル`
for x (<->~1ドル)((1ドル/x%x==1))

Attempt This Online!

Answer 3

Vyxal r, 8 bytes

Ǐo:?/‹ḊΠ

Try it Online!

Ǐo # prime factors excluding x
 : # Duplicate
 ?/ # Input / n (vectorised)
 ‹ # Decremented (vectorised)
 Ḋ # Is divisible by corresponding prime factor (vectorised)
 Π # Take the product (0 for empty list)

Answer 4

J, ²² 19 bytes

1<q:(-:*#@[)*:@q:|]

Try it online!

^{-3 after reading Bubbler's analysis.}

• *:@q:|] Mods input by square of its prime factors (vectorized).
• -: Does that match the list of prime factors?
• *#@[ Times the length of the prime factors.
• 1< Is that greater than 1?

• Bubbler: I think you need to include 1< in the submission. Note: J's falsy values are nonempty arrays having 0 as their first atom.
• Jonah: @Bubbler Thanks, fixed now. I had stopped reading after "Two classes of values..."

Answer 5

Retina 0.8.2, (削除) 73 (削除ここまで) 62 bytes

.+
$*
^((.)*)(?=1円*$)(?<!^3円+(..+))(?!((?<-2>1円)+)(?(2)^)4円*$)

Try it online! Link includes test cases. Outputs 0 for a Guiga number, 1 if not. Explanation:

.+
$*

Convert n to unary.

^((.)*)

Match an integer p=1円, but also as a count 2円, where...

(?=1円*$)

... p must be a factor of n, ...

(?<!^3円+(..+))

... p must not have a nontrivial proper factor 3円, and...

(?!((?<-2>1円)+)(?(2)^)4円*$)

... n-p must be zero (in which case n is not composite) or not divisible by p2, which is calculated by matching 1円 2円 times, and then captured, so that it can be easily repeated using 4円.

Edit: Saved 11 bytes thanks to @Deadcode pointing out that I don't need to check that p is at least 2, and in fact also allowing p=0 means that the program works for n=0 (although not required by the question) at no extra cost.

• Deadcode: -10 bytes
• Neil: @Deadcode So my test for p>1 is unnecessary? That would actually save me 11 bytes if that's the case.
• Deadcode: Indeed it is unnecessary. So with that, my regex will be only 3 bytes shorter than yours.
• Deadcode: But with correct handling of zero, your regex becomes 56 bytes, identical in length to mine: ^((.)*)(?=1円*$)(?<!^3円+(..+))(?!((?<-2>1円)+)(?(2)^)4円*$) (56) versus ^(x*)(?<!^2円+(x+x))(1円)*$(?<=(?!\B1円*$)(?>(?<-3>x)*))|^$ (56)
• Neil: @Deadcode Although it beats me why I went to the length of writing ^((.)+)(?<=..) instead of ^((.){2,}) in the first place...

Answer 6

Jelly, 9 bytes

Æfð_ọḟ>1Ȧ

Try it online!

Æfḟð_ọḷ’Ȧ

Try it online!

I already lost, but figured I'd post them since they're somewhat different 9-byters.

How these work

The condition \$p_i \mid \left( \frac n {p_i} -1 \right)\$ can be translated to

$$ \frac{n}{p_i}-1 \equiv 0 \quad(\operatorname{mod} \ p_i) \\ \frac{n}{p_i} \equiv 1 \quad(\operatorname{mod} \ p_i) \\ n \equiv p_i \quad(\operatorname{mod} \ p_i^2) $$

So \$n-p_i\$ (equivalently, \$p_i-n\$) must be divisible by \$p_i\$ at least twice.

Æfð_ọḟ>1Ȧ Monadic link; input = n
Æf List of prime factors of n (= L)
 ð...... Call ... as a dyadic chain, left = L, right = n
 ọ How many times each of...
 _ L - n
 ...is divisible by...
 ḟ Remove any occurrences of n from L
 (missing positions are treated as 0, so ọ gives 0)
 >1Ȧ Test if the result is nonempty list of all 2s or above
Æfḟð_ọḷ’Ȧ Monadic link; input = n
Æfḟ Remove any occurrences of n from prime factors of n (= L)
 ð..... Call ... as a dyadic chain, left = L, right = n
 _ọḷ How many times each of L-n is divisible by each of L
 ’Ȧ Test if the result, decremented, is nonempty with all nonzero

Answer 7

Ruby, 50 bytes

->n{(2...z=n).all?{|c|z%c>0||n/c%c==1&&z/=c}&&z<n}

Try it online!

So what?

->n{(2...z=n).all?

Check every number between 2 and n-1, use a temporary variable to skip over composite divisors.

{|c|z%c>0

If c is divisor of z then it's also a prime divisor of n, if not we can skip this number.

||n/c%c==1

Check if n/c-1 can be divided by c

&&z/=c}

At this point, we must divide z by c before continuing. Once is enough, because if n/c-1 can be divided by c, then n can't be divided by c more than once.

&&z<n}

Final check: did we divide z at least once? If not, then n is a prime number.

Answer 8

Python 2, 85 bytes

e=n=input();k=w=0;i=1
while~-n:
 i+=1
 while n%i<1:k+=(e/i-1)%i;n/=i;w+=1
print k<1<w

Try it online!

-14 bytes thanks to @ovs

• Tipping Octopus: Doing k=w=i=1 and k<2<w saves two bytes

Answer 9

JavaScript (ES6), (削除) 59 56 (削除ここまで) 53 bytes

Returns a Boolean value.

n=>(k=2,g=j=>j%k?k++<j&&g(j):n/k%k-1?g:1+g(j/k))(n)>1

Try it online!

Commented

n => ( // n = input
 k = 2, // k is the prime divisor, starting at 2
 g = j => // g is a recursive function taking the quotient j
 j % k ? // if k is not a divisor of j:
 k++ < j && // stop if k is greater than or equal to j
 g(j) // otherwise, do a recursive call with j unchanged
 // and k + 1
 : // else:
 n / k % k // if (n / k) modulo k
 - 1 ? // is not equal to 1:
 g // stop the recursion and yield g, which turns the
 // result into a non-numeric string and forces the
 // final test to fail, whatever happened before
 : // else:
 1 + // add 1 to the result
 g(j / k) // do a recursive call with j = j / k
)(n) // initial call with j = n
> 1 // return true if there were at least 2 prime divisors
 // satisfying the Giuga test

• Arnauld: Props to the creativity of the syntax highlighter which draws g in black, red and blue in the same piece of code! \o/
• Arnauld: Ah well, not anymore ... :-/ See revision 2.

Answer 10

05AB1E, 9 bytes

f©/<0K®Öß

Outputs 1 as truthy and either 0/"" as falsey.

Try it online or verify some more test cases.

Explanation:

f # Get all unique prime factors of the (implicit) input
 © # Store this list in variable `®` (without popping)
 / # Divide the input by each of these
 < # Decrease it by 1
 0K # Remove all 0s
 ®Ö # Check of each if it's divisible by their initial values `®`
 ß # Pop and push the minimum of this list ("" for empty lists)
 # (after which it is output implicitly as result)

Answer 11

Brachylog, 16 bytes

N0ḋṀ{;N0↔÷;?%}v1

Try it online!

Answer 12

Regex (ECMAScript 2018 / Python^regex / .NET), (削除) 83 (削除ここまで) (削除) 79 (削除ここまで) (削除) 64 (削除ここまで) 49 bytes

^(x(x*))(?<!^3円+(x+x))(?!(?=1円*(1円2円+$))4円*$)1円*$

-15 bytes (79 → 64) thanks to H.PWiz
-8 bytes (64 → 56) by squaring instead of doing division (thanks to H.PWiz for the idea)
-7 bytes (56 → 49) thanks to H.PWiz - now beats the original .NET-only version!

Returns a non-match for Giuga numbers.

Try it online! - ECMAScript 2018
Try it online! - Python _{^{import regex}} (very slow)
Try it online! - .NET

The commented version below is a 54 byte version that behaves correctly with an input of zero, and returns a match for Giuga numbers. (Its length would be 52 bytes if returning a non-match for Giuga numbers.)

The underlying squaring/multiplication algorithm is explained in this post.

^ # tail = N = input number
(?! # Negative lookahead - Assert that this cannot match
 # Cycle 1円 through all the prime divisors of N
 (x(x*)) # 1円 = conjectured non-composite divisor of N; 2円 = 1円-1
 # tail -= 1円; head = 1円
 (?<!^3円+(x+x)) # Assert head is not composite, i.e. is prime or <2
 # Assert that tail is not divisible by 1円 * 1円
 (?! # Negative lookahead - Assert that this cannot match
 # Calculate 4円 = 1円 * 1円; this will fail to match if the result would
 # be greater than tail.
 (?=
 1円* # We can use this shortcut thanks to tail already being
 # checked for divisibility by 1円 later.
 (1円2円+$) # 4円 = 1円 * 1円
 )
 4円*$ # Assert that tail is divisible by 4円
 )
 1円*$ # Assert N is divisible by 1円
)
x # Prevent N == 0 from matching

Regex (.NET), (削除) 57 (削除ここまで) (削除) 53 (削除ここまで) bytes

Now obsoleted by the ECMAScript 2018 / .NET version above.

Regex (ECMAScript+(?^=)^RME ), 50 bytes

^(x(x*))(?^1!(xx+)3円+$)(?!(?=1円*(1円2円+$))4円*$)1円*$

Try it on replit.com - RegexMathEngine

This is a port using lookinto instead of variable-length lookbehind.

Regex (ECMAScript+(?*)^RME / PCRE2 _^v10.35+), 58 bytes

^(?*(x(x*))(1円*$))(?!3円(xx+)4円+$)1円(?!(?=1円*(1円2円+$))5円*$)

Try it on replit.com - RegexMathEngine
Attempt This Online! - PCRE2 v10.40+

This is a port using molecular lookahead instead of variable-length lookbehind. It is far, far faster, since it does not place a divisibility test after an is-prime test (and to do so would not be better golf, as far as I can tell); on my PC it can test every number from \0ドル\$ to \66200ドル\$ in 5.2 minutes (whereas the ECMAScript 2018 version takes weeks or maybe more) and can even test \2214408306ドル\$ in 6.4 minutes.

^ # tail = N = input number
(?! # Negative lookahead - Assert that this cannot match
 # Cycle 1円 through all the prime divisors of N
 (?*(x(x*))(1円*$)) # Cycle 1円 through all of the divisors of N, including N
 # itself; 2円 = 1円-1; 3円 = N-1円 == tool to make tail = 1円
 (?!3円(xx+)4円+$) # Assert 1円 is prime or 1円 < 2.
 1円 # tail -= 1円
 # Assert that tail is not divisible by 1円 * 1円
 (?! # Negative lookahead - Assert that this cannot match
 # Calculate 5円 = 1円 * 1円
 (?=
 1円* # We can use this shortcut thanks to tail already being
 # checked for divisibility by 1円 later.
 (1円2円+$) # 5円 = 1円 * 1円
 )
 5円*$ # Assert that tail is divisible by 5円
 )
)
x # Prevent N == 0 from matching

\$\large\textit{Full programs}\$

Retina 0.8.2, (削除) 63 (削除ここまで) (削除) 59 (削除ここまで) 55 bytes

.+
$*
^(.+)(?<!^2円+(.+.))(1円)*$(?<=(?!\B1円*$)(?>(?<-3>.)*))

Takes its input in decimal. Outputs 1 if input is a Guiga number, 0 if not.

Try it online!

• Neil: Save 4 bytes by outputting 0 if the input is a Guiga number, 1 if not.
• Deadcode: @Neil Oh right, thanks. Silly me – the reason I didn't do that is that with the correct handling of zero, the regex is the same length either way. It was only later that I noticed the problem said handling of zero wasn't necessary, and after removing that, I forgot to reevaluate my decision of whether to invert the match/non-match logic,
• H.PWiz: For ecmascript, you can use an abbreviated division since you're dividing by a prime. I have also included another save: ^(x(x*))(?<!^3円+(x+x))(?=1円*$)((?=(x(x*))(?=5円*$)(2円6円*$))7円(?!1円*$)|$)
• Deadcode: @H.PWiz Thanks! Yep, I misremembered that rule as both the dividend and divisor needing to be powers of the same prime, otherwise I would have used that abbreviated form already. As for your other save, I look forward to finding out what it was.
• H.PWiz: Oh, and another save: ^(x(x*))(?<!^3円+(x+x))(?=(x(x*))(?=4円*$)(2円5円*$)|)(?!6円1円+$)1円*$. I thought I included the first save in the previous post... Now you get two in one

Answer 13

MATL, (削除) 13 (削除ここまで) 12 bytes

YfG-t?6MU\~A

Try it online!

1 for Giuga number, either 0 or an empty vector for non-Giuga number - both of which MATL considers falsy.

(note: had previously posted a 9 byte version which was wrong)

Explanation:

\$p_i \mid \left( \frac n {p_i} -1 \right) \Longrightarrow p_i^2 \mid \left( n - {p_i} \right) \Longrightarrow p_i^2 \mid \left( {p_i} - n \right)\$

1. Yf - get the prime factors of the input (if 1 is the input, Yf returns an empty vector; primes return themselves)
2. G- - subtract the input from each factor (let's call this S = \${p_i} - n \$)
3. t? - is it truthy? (for 1 this is an empty vector; for primes it's a 0; either way, falsey)
4. 6M - If so, bring back a copy of the list of factors
5. U - square each one
6. \ - compute the mod of S with respect to these squares
7. ~A - And check if that is all 0s

If the check at step 3 failed, that falsy S is left on the stack. If it succeeded, the result of the final step is left on the stack.

---

Alternate 12 byter: _tYf+t5MU\~* Try it online!

Answer 14

Japt, 18 bytes

k f<U £/XÉ vXÃâ 1円

Try it

k - prime factors
f<U - filter out U(input)
£..Ã - map X-> :
/XÉ > U/X-1
vX > divisible by X?
â - get unique elements
1円 - is [1] ?