Regex 🐇
(PCRE2 v10.35+), 60 59 54 52 bytes
^((?*(?=(xx+?)\2*$|)((?=x\2)(x+)\4*(?=\4$))*+x+)x)*$
Takes its input in unary, as a string of x
characters whose length represents the number. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method.)
Attempt This Online! - PCRE2 v10.40+
The 🐇
output method takes advantage of an aspect of regex that's normally hidden: the backtracking paths that aren't taken. In normal use, all traces of the avenues of potential alternative matches are erased when a final match is found. But in 🐇
, they're all taken and counted, allowing a number to be outputted that's larger than the input. For scalar unary input, this provides a strict superset of the power of returning a number via the matched substring or a capture group (either of which can only return values less than or equal to the input), except that there can be no extra state of returning "no match" (in 🐇
, that just returns \$0\$).
The limitation of having to work within the space of the input is still present. 🐇
can do combinations of multiplication and addition to yield numbers larger than the input, but it can't do subsequent tests on those results (it can only do tests on intermediate results calculated using capture groups and tail). So for example in this problem, the regex can't just directly search for the smallest number that is divisible by all numbers in the range \$[1,n]\$, because that number is not only larger than the input, it's too large even to be able to emulate using number base arithmetic (and even if that were possible, it would not golf well). So, this regex uses an algorithm different from all of the other answers:
It takes the base prime \$p\$ of every prime power \$p^k\le n\$, and calculates the product of that list of numbers. And because each \$p\$ will occur \$\max \left\{ k \, \middle| \, p^k \le n \right\}\$ times in that list, this product is the same as the product of the prime powers themselves would be, if only the largest from each base prime were included.
The prime power portion is based on my prime powers answer Neil's prime powers answer (which is in turn based on my earliest CGCC answer). In the prime powers challenge, my regex is shorter, but for the purposes of this challenge, his regex (after some extra golfing) allows capturing the smallest prime factor, thus golfing down the overall regex by 1 6 bytes.
^ # tail = N = input number
( # Loop the following:
(?* # Non-atomic lookahead:
# M = tail, which cycles from N down to 1
(?=(xx+?)\2*$|) # \2 = smallest prime factor of M if M ≥ 2;
# otherwise, leave \2 unchanged in PCRE, or
# unset in ECMAScript
(
(?=x\2) # Keep iterating until tail ≤ \2, and because of
# what \2 is, this means at the end of the loop,
# either tail == \2 (if M is a prime power) or
# tail == 1 (if M is not a prime power)
(x+)\4*(?=\4$) # tail = \4 = {largest proper divisor of tail}
# = tail / {smallest prime factor of tail}
)*+ # Iterate the above as many times as possible,
# minimum zero, and lock in the result using a
# possessive quantifier.
x+ # Multiply number of possible matches by tail
)
x # tail -= 1
)* # Loop the above a minimum of 0 times
$ # Assert that at the end of the above loop, tail == 0
This even returns a correct value for \$n=0\$, while the earlier 60 byte version did not (and needed to be extended to 63 bytes to do so).
A list of other answers that return \$f(0)=1\$ correctly, complete at the time of this edit: AWK, Dyalog APL, J, Japt, Julia v0.7+ (but it was v0.6 at the time of posting, and didn't support it then), MATLAB, MATL, Maxima (with functs), Minkolang (1st answer), Nibbles, PHP, Pari/GP, Perl 5, Perl 6, Pyth, Python (with SymPy), Python (with math), Python, QBIC, Rexx, Vyxal. (Not tested: 8th, Axiom, Hoon)
2
and6
were removed from the list of multiples. Can please you clarify the rules? \$\endgroup\$