Regex (.NET), 57 53 bytes
^(x+)(?<!^\2+(x+x))(\1)*$(?<=(?!\B\1*$)(?>(?<-3>x)*))
Takes its input in unary, as the length of a string of x
s. Returns a non-match for Giuga numbers.
Try it online!
The commented version below is a 58 byte version that behaves correctly with an input of zero, and returns a match for Giuga numbers. (Its length would be 56 bytes if returning a non-match for Giuga numbers, because ^(?!
...)x
could be changed to ^
...|^$
.)
^ # tail = N = input number
(?! # Negative lookahead - Assert that this cannot match
# Cycle \1 through all the prime divisors of N
(x+) # \1 = conjectured non-composite divisor of N;
# tail -= \1; head = \1
(?<!^\2+(x+x)) # Assert head is not composite, i.e. is prime or <2
(\1)*$ # Assert N is divisible by \1;
# Divide tail / \1, stored as the capture count of \3;
# tail = 0; head = N
(?<=
# Assert either that head is not divisible by \1, or that head == N in
# the case that N!=0. The latter prevents the outer negative lookahead
# from matching for prime values of N or N==1. Ideally we'd not have
# N==0 treated differently, so that this would also prevent N==0 from
# matching, but that would require using something other than "\B",
# such as "((?!\1*$)|$)" instead of "(?!\B\1*$)" with "x" at the end,
# which would make the regex 1 byte longer in total.
(?! # Negative lookahead - Assert that this cannot match
\B # Assert either that N==0, or that head != N
# and
\1*$ # Assert tail is divisible by \1
)
(?>(?<-3>x)*) # tail = capture count of \3 = (N-\1)/\1 = N/\1-1;
# there is no need to follow this with something like
# "(?(3)$)", because we wrapped it in an atomic group,
# and it is guaranteed that N/\1-1 <= N
)
)
x # Prevent N==0 from matching
Regex (ECMAScript 2018), 83 79 bytes
^(x(x*))(?<!^\3+(x+x))(?=\1*$)((?=(x(x*))(?=\5*$)(?=\2+$)(\2\6*$))\7(?!\1*$)|$)
Returns a non-match for Giuga numbers.
Try it online!
The commented version below is a 84 byte version that behaves correctly with an input of zero, and returns a match for Giuga numbers. (Its length would be 82 bytes if returning a non-match for Giuga numbers.)
The division algorithm is explained in my Division and remainder 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
(?=\1*$) # Assert N is divisible by \1
(
# Calculate \5 = tail / \1; only works for tail > 0
(?=
(x(x*)) # \5 = quotient - find the largest that matches the
# following assertions; \6 = \5-1; tail -= \5
(?=\5*$) # assert tail is divisible by quotient
(?=\2+$) # assert tail is positive and divisible by divisor-1
(\2\6*$) # assert tail-(divisor-1) is divisible by quotient-1;
# \7 = tool to make tail = \5
)\7 # tail = \5 = (N-\1)/\1 = N/\1-1
(?!\1*$) # Assert tail is not divisible by \1
|
$ # Assert tail==0; prevents prime values of N or N==1
# from making the outer negative lookahead match.
)
)
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\$