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

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)

Answer 2

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?

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

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 5

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 6

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.

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

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

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

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