# Is it a Giuga number?

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 , 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

• Brownie points for beating or tying my 9 byte Jelly answer (outputs 1/0) Jun 30, 2021 at 23:32
• 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)]& Jul 6, 2021 at 6:53

# 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)

• 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’ọ@.) Jul 1, 2021 at 11:18

# 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:

>factor $1 for x (<->~$1)(($1/x%x==1)) Attempt This Online! # Vyxalr, 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)  # J, 22 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? # 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 p², 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. • -10 bytes Jun 30, 2022 at 18:15 • @Deadcode So my test for p>1 is unnecessary? That would actually save me 11 bytes if that's the case. – Neil Jun 30, 2022 at 23:48 • Indeed it is unnecessary. So with that, my regex will be only 3 bytes shorter than yours. Jul 1, 2022 at 0:03 • 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)*$(?<=(?!\B\1*$)(?>(?<-3>x)*))|^$ (56) Jul 1, 2022 at 0:18
• @Deadcode Although it beats me why I went to the length of writing ^((.)+)(?<=..) instead of ^((.){2,}) in the first place...
– Neil
Jul 1, 2022 at 0:24

# 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


# 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.

# 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

• Doing k=w=i=1 and k<2<w saves two bytes Jul 2, 2021 at 3:54

# 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

• Props to the creativity of the syntax highlighter which draws g in black, red and blue in the same piece of code! \o/ Jul 1, 2021 at 0:13
• Ah well, not anymore ... :-/ See revision 2. Jul 1, 2021 at 9:04

# 05AB1E, 9 bytes

f©/<0K®Öß


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

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)


# Brachylog, 16 bytes

N⁰ḋṀ{;N⁰↔÷;?%}ᵛ1


Try it online!

# Regex (ECMAScript 2018 / Pythonregex / .NET), 837964 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), 5753 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


# Retina 0.8.2, 6359 55 bytes

.+
$* ^(.+)(?<!^\2+(.+.))(\1)*$(?<=(?!\B\1*$)(?>(?<-3>.)*))  Takes its input in decimal. Outputs 1 if input is a Guiga number, 0 if not. Try it online! • Save 4 bytes by outputting 0 if the input is a Guiga number, 1 if not. – Neil Jun 30, 2022 at 23:37 • @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, Jul 1, 2022 at 0:01 • 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*$)|$) Jul 9, 2022 at 0:01
• @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. Jul 9, 2022 at 0:06
• 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 Jul 9, 2022 at 0:06

# 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!

# 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] ?