20
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ Brownie points for beating or tying my 9 byte Jelly answer (outputs 1/0) \$\endgroup\$ – caird coinheringaahing Jun 30 at 23:32
  • 1
    \$\begingroup\$ @LuisMendo Well, I can't read! Corrected, thanks :) \$\endgroup\$ – caird coinheringaahing Jul 1 at 13:28
  • \$\begingroup\$ 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)]& \$\endgroup\$ – theorist Jul 6 at 6:53

11 Answers 11

9
\$\begingroup\$

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)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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’ọ@.) \$\endgroup\$ – Unrelated String Jul 1 at 11:18
6
\$\begingroup\$

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?
\$\endgroup\$
2
6
\$\begingroup\$

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)
\$\endgroup\$
0
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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 , which is calculated by matching \1 \2 times, and then captured, so that it can be easily repeated using \4.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ Doing k=w=i=1 and k<2<w saves two bytes \$\endgroup\$ – Tipping Octopus Jul 2 at 3:54
3
\$\begingroup\$

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
\$\endgroup\$
2
  • 5
    \$\begingroup\$ Props to the creativity of the syntax highlighter which draws g in black, red and blue in the same piece of code! \o/ \$\endgroup\$ – Arnauld Jul 1 at 0:13
  • 2
    \$\begingroup\$ Ah well, not anymore ... :-/ See revision 2. \$\endgroup\$ – Arnauld Jul 1 at 9:04
2
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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] ?
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.