We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.

Return to Revisions

Regex (ECMAScript), (削除) 35 (削除ここまで) 33 bytes

-2 bytes thanks to H.PWiz

^(?!((x+)(?=2円*$)x+)(?!2円*$)1円+$)

Try it online!

The 35 byte version was written in 2014 by teukon and me.

This works by asserting that for any \$a\$ and \$b\$, two proper divisors of \$n\$ where \$a>b\$, \$n-a\$ will always be divisible by \$b\$.

This will always be true when \$n\$ is of the form \$p^k\$ (a prime power), because we will have \$a=p^c\$ and \$b=p^d\$ where \0ドル \le c<d<k\$, thus \$a\$ will be divisible by \$b\$, and since \$n-a\$ is divisible by \$a\$, it too will be divisible by \$b\$.

But if \$n\$ is not of the form \$p^k\$, there will always be at least one counterexample \$a,b\$ such that \$n-a\$ is not divisible by \$b\$. For example, let one of the divisors be a prime power \$x=p^q>1\$ such that \$p^{q+1}\$ is not a divisor of \$n\$, and let the other one be \$y=n/x>1\$. Distribute \$x,y\$ into \$a,b\$ depending on which is larger. They will be coprime, so their least common multiple will be \$n\$. Thus, no number smaller than \$n\$, including \$n-a\$, will be divisible by both \$a\$ and \$b\$, and since \$n-a\$ is divisible by \$a\$, it will not be divisible by \$b\$.

# For the purpose of these comments, the input number will be referred to as N.
^(?! # It is not true that...
 ((x+)(?=2円*$)x+) # there exists a 2円 which is a divisor of N,
 # and exists a 1円 such that 1円 > 2円
 (?!2円*$) # such that N-1円 is not divisible by 2円
 1円+$ # and 1円 is a proper divisor of N
)

Regex (.NET), 33 (32🐌) bytes

^(?!((x+)x+)\B(?>1円*?(?<=^2円+))$)

Try it online!

This uses the same algorithm as Bubbler's APL answer:

# For the purpose of these comments, the input number will be referred to as N.
^(?! # It is not true that...
 ((x+)x+) # There exists a 2円 and 1円 such that 0 < 2円 < 1円
 \B # and 1円 < N (literally, 0 < 1円 < N or N == 0)
 (?> # such that the first (atomic) match we find to this:
 # Advance to the least common multiple of 1円 and 2円
 1円*? # Find the first multiple of 1円
 (?<=^2円+) # that is also divisible by 2円
 )
 $ # equals N
)

This offers no advantage over the ECMAScript version, which is also 33 bytes but much faster and also works in .NET. However, the ((x+)x+) can be changed to ((x+)+), dropping the size by 1 byte (to 32 bytes) with no loss of correct functionality – but the regex exponentially explodes in slowness:

^(?!((x+)+)\B(?>1円*?(?<=^2円+))$)

Try it online!

In playing around with this, I came up with a 29 (28🐌) byte ECMAScript 2018 / .NET regex that matches numbers of the form \$p^k\$ where \0ドル \le k \le 2\$:

^(?!((x+)x+)1円+$(?<!^1円+2円+))

Retina 0.8.2, (削除) 41 (削除ここまで) 39 (38🐌) bytes

39 byte version:

.+
$*
^(?!((1+)(?=2円*$)1+)(?!2円*$)1円+$)

Try it online!

38 byte exponential slowdown 🐌 version:

.+
$*
^(?!((1+)+)\B(?>1円*?(?<=^2円+))$)

Try it online!