# 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
• @LuisMendo Well, I can't read! Corrected, thanks :) Jul 1, 2021 at 13:28
• 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

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


# 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! # 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 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 at 23:48 • Indeed it is unnecessary. So with that, my regex will be only 3 bytes shorter than yours. Jul 1 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 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 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ḟ          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

# Brachylog, 16 bytes

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


Try it online!

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


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


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

# Regex (.NET), 57 53 bytes

^(x+)(?<!^\2+(x+x))(\1)*$(?<=(?!\B\1*$)(?>(?<-3>x)*))


Takes its input in unary, as the length of a string of xs. Returns a non-match for Giuga numbers.

Try it online!

The commented version below is a 58 byte version that behaves correctly with an input of zero, and returns a match for Giuga numbers. (Its length would be 56 bytes if returning a non-match for Giuga numbers, because ^(?!...)x could be changed to ^...|^$.) ^ # tail = N = input number (?! # Negative lookahead - Assert that this cannot match # Cycle \1 through all the prime divisors of N (x+) # \1 = conjectured non-composite divisor of N; # tail -= \1; head = \1 (?<!^\2+(x+x)) # Assert head is not composite, i.e. is prime or <2 (\1)*$             # Assert N is divisible by \1;
# Divide tail / \1, stored as the capture count of \3;
# tail = 0; head = N

(?<=
# Assert either that head is not divisible by \1, or that head == N in
# the case that N!=0. The latter prevents the outer negative lookahead
# from matching for prime values of N or N==1. Ideally we'd not have
# N==0 treated differently, so that this would also prevent N==0 from
# matching, but that would require using something other than "\B",
# such as "((?!\1*$)|$)" instead of "(?!\B\1*$)" with "x" at the end, # which would make the regex 1 byte longer in total. (?! # Negative lookahead - Assert that this cannot match \B # Assert either that N==0, or that head != N # and \1*$       # Assert tail is divisible by \1
)

(?>(?<-3>x)*)  # tail = capture count of \3 = (N-\1)/\1 = N/\1-1;
# there is no need to follow this with something like
# "(?(3)$)", because we wrapped it in an atomic group, # and it is guaranteed that N/\1-1 <= N ) ) x # Prevent N==0 from matching  # Regex (ECMAScript 2018), 83 79 bytes ^(x(x*))(?<!^\3+(x+x))(?=\1*$)((?=(x(x*))(?=\5*$)(?=\2+$)(\2\6*$))\7(?!\1*$)|$)  Returns a non-match for Giuga numbers. Try it online! The commented version below is a 84 byte version that behaves correctly with an input of zero, and returns a match for Giuga numbers. (Its length would be 82 bytes if returning a non-match for Giuga numbers.) The division algorithm is explained in my Division and remainder 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 (?=\1*$)           # Assert N is divisible by \1

(
# Calculate \5 = tail / \1; only works for tail > 0
(?=
(x(x*))    # \5 = quotient - find the largest that matches the
#      following assertions; \6 = \5-1; tail -= \5
(?=\5*$) # assert tail is divisible by quotient (?=\2+$)   # assert tail is positive and divisible by divisor-1
(\2\6*$) # assert tail-(divisor-1) is divisible by quotient-1; # \7 = tool to make tail = \5 )\7 # tail = \5 = (N-\1)/\1 = N/\1-1 (?!\1*$)       # Assert tail is not divisible by \1
|
$# Assert tail==0; prevents prime values of N or N==1 # from making the outer negative lookahead match. ) ) x # Prevent N==0 from matching  ### $$\\large\textit{Full programs}\$$ # Retina 0.8.2, 63 59 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 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 at 0:01