# 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 at 23:32
• @LuisMendo Well, I can't read! Corrected, thanks :) Jul 1 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 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)
Æ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 at 11:18

# J, 22 19 bytes

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


Try it online!

• *:@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?

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


# 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


# 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! # Retina 0.8.2, 73 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.

^.$|  Special-case 1, as all of its prime factors satisfy the relation but it's not composite so it's excluded. ^((.)+)  Match an integer p=\1, but also as a count \2, where... (?=\1*$)


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

(?<=..)


... p must be at least 2, ...

(?<!^\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.

# 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 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 at 0:13
• Ah well, not anymore ... :-/ See revision 2. Jul 1 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!

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