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}\$
.+
$*
^(.+)(?<!^\2+(.+.))(\1)*$(?<=(?!\B\1*$)(?>(?<-3>.)*))
Takes its input in decimal. Outputs 1
if input is a Guiga number, 0
if not.
Try it online!
1
/0
) \$\endgroup\$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\$