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

14 Answers 14

10
\$\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\$ Jul 1, 2021 at 11:18
8
+500
\$\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\$
7
\$\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
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
5
\$\begingroup\$

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

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

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\$
4
\$\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\$ Jul 2, 2021 at 3:54
4
\$\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, 2021 at 0:13
  • 2
    \$\begingroup\$ Ah well, not anymore ... :-/ See revision 2. \$\endgroup\$
    – Arnauld
    Jul 1, 2021 at 9:04
4
\$\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\$
4
\$\begingroup\$

Brachylog, 16 bytes

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Regex (ECMAScript 2018 / Pythonregex / .NET), 83 79 64 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), 57 53 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

\$\large\textit{Full programs}\$

Retina 0.8.2, 63 59 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!

\$\endgroup\$
6
  • \$\begingroup\$ Save 4 bytes by outputting 0 if the input is a Guiga number, 1 if not. \$\endgroup\$
    – Neil
    Jun 30, 2022 at 23:37
  • \$\begingroup\$ @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, \$\endgroup\$
    – Deadcode
    Jul 1, 2022 at 0:01
  • 1
    \$\begingroup\$ 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*$)|$) \$\endgroup\$
    – H.PWiz
    Jul 9, 2022 at 0:01
  • \$\begingroup\$ @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. \$\endgroup\$
    – Deadcode
    Jul 9, 2022 at 0:06
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – H.PWiz
    Jul 9, 2022 at 0:06
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\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.