Skip to main content
We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.
Code Golf

Return to Answer

remove RegexMathEngine harness, because a bug triggered by the 59->54 byte golf still happens even in -xpbr mode
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55

Regex πŸ‡ (ECMAScript+(?*)x*+RME / PCRE2PCRE2 v10.35+), (ε‰Šι™€) 60 (ε‰Šι™€γ“γ“γΎγ§) (ε‰Šι™€) 59 (ε‰Šι™€γ“γ“γΎγ§) (ε‰Šι™€) 54 (ε‰Šι™€γ“γ“γΎγ§) 52 bytes

Attempt This Online! - PCRE2 v10.40+
RegexMathEngine : call with regex -X -xml,pq -nx -t0..17 --line-buffered -f regex.txt where regex.txt contains the regex with no newline

Regex πŸ‡ (ECMAScript+(?*)x*+RME / PCRE2 v10.35+), (ε‰Šι™€) 60 (ε‰Šι™€γ“γ“γΎγ§) (ε‰Šι™€) 59 (ε‰Šι™€γ“γ“γΎγ§) (ε‰Šι™€) 54 (ε‰Šι™€γ“γ“γΎγ§) 52 bytes

Attempt This Online! - PCRE2 v10.40+
RegexMathEngine : call with regex -X -xml,pq -nx -t0..17 --line-buffered -f regex.txt where regex.txt contains the regex with no newline

Regex πŸ‡ (PCRE2 v10.35+), (ε‰Šι™€) 60 (ε‰Šι™€γ“γ“γΎγ§) (ε‰Šι™€) 59 (ε‰Šι™€γ“γ“γΎγ§) (ε‰Šι™€) 54 (ε‰Šι™€γ“γ“γΎγ§) 52 bytes

Attempt This Online! - PCRE2 v10.40+

-2 bytes; correct a subtle error/omission in the explanation; replace currently nonfunctional replit.com link with RME usage note
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55

Regex πŸ‡ (ECMAScript+(?*)x*+RME / PCRE2 v10.35+), (ε‰Šι™€) 60 (ε‰Šι™€γ“γ“γΎγ§) (ε‰Šι™€) 59 (ε‰Šι™€γ“γ“γΎγ§) 54(ε‰Šι™€) 54 (ε‰Šι™€γ“γ“γΎγ§) 52 bytes

^((?*(?=(xx+?)2円*$|)((?=x2円)(?=(x+)4円*(4円+$?=4円$))5円)*+x+)x)*$

Attempt This Online! Attempt This Online! - PCRE2 v10.40+
Try it on replit.com - ECMAScript+(?*)+x*+ (RegexMathEngineRegexMathEngine : call with regex -X -xml,pq -nx -t0..17 --line-buffered -f regex.txt) where regex.txt contains the regex with no newline

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 \$k\$\$\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.

^ # 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
 (
 (?=x2円) # 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円+$)?=4円$) # tail = 4円 = {largest proper divisor of tail}
 # = tail / {smallest prime factor of tail};
  # 5円 = tail - 4円
 5円 #/ tail{smallest =prime tailfactor -of (tail - 4円) = 4円}
 )*+ # 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

Regex πŸ‡ (ECMAScript+(?*)x*+RME / PCRE2 v10.35+), (ε‰Šι™€) 60 (ε‰Šι™€γ“γ“γΎγ§) (ε‰Šι™€) 59 (ε‰Šι™€γ“γ“γΎγ§) 54 bytes

^((?*(?=(xx+?)2円*$|)((?=x2円)(?=(x+)(4円+$))5円)*+x+)x)*$

Attempt This Online! - PCRE2 v10.40+
Try it on replit.com - ECMAScript+(?*)+x*+ (RegexMathEngine -xml,pq)

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 \$k\$ 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.

^ # 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
 (
 (?=x2円) # 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円 = {largest proper divisor of tail}
 # = tail / {smallest prime factor of tail};
  # 5円 = tail - 4円
 5円 # tail = tail - (tail - 4円) = 4円
 )*+ # 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

Regex πŸ‡ (ECMAScript+(?*)x*+RME / PCRE2 v10.35+), (ε‰Šι™€) 60 (ε‰Šι™€γ“γ“γΎγ§) (ε‰Šι™€) 59 (ε‰Šι™€γ“γ“γΎγ§) (ε‰Šι™€) 54 (ε‰Šι™€γ“γ“γΎγ§) 52 bytes

^((?*(?=(xx+?)2円*$|)((?=x2円)(x+)4円*(?=4円$))*+x+)x)*$

Attempt This Online! - PCRE2 v10.40+
RegexMathEngine : call with regex -X -xml,pq -nx -t0..17 --line-buffered -f regex.txt where regex.txt contains the regex with no newline

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.

^ # 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
 (
 (?=x2円) # 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
express the features added on top of ECMAScript by RME in a more concise fashion
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55

Regex πŸ‡ (ECMAScript+(?*)+()++x*+RME RME / PCRE2 v10.35+), (ε‰Šι™€) 60 (ε‰Šι™€γ“γ“γΎγ§) (ε‰Šι™€) 59 (ε‰Šι™€γ“γ“γΎγ§) 54 bytes

Attempt This Online! - PCRE2 v10.40+
Try it on replit.com - ECMAScript+(?*)+()++x*+ (RegexMathEngine -xml,pq)

Regex πŸ‡ (ECMAScript+(?*)+()++RME / PCRE2 v10.35+), (ε‰Šι™€) 60 (ε‰Šι™€γ“γ“γΎγ§) (ε‰Šι™€) 59 (ε‰Šι™€γ“γ“γΎγ§) 54 bytes

Attempt This Online! - PCRE2 v10.40+
Try it on replit.com - ECMAScript+(?*)+()++ (RegexMathEngine -xml,pq)

Regex πŸ‡ (ECMAScript+(?*)x*+RME / PCRE2 v10.35+), (ε‰Šι™€) 60 (ε‰Šι™€γ“γ“γΎγ§) (ε‰Šι™€) 59 (ε‰Šι™€γ“γ“γΎγ§) 54 bytes

Attempt This Online! - PCRE2 v10.40+
Try it on replit.com - ECMAScript+(?*)+x*+ (RegexMathEngine -xml,pq)

restore augmented-ECMAScript mode in the RegexMathEngine test harness, as the atomic group bug is now fixed
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55
Loading
fix accuracy of a comment
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55
Loading
add the RegexMathEngine test harness back, as it can work fine in -xpbr mode
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55
Loading
slight rewording for better accuracy/conciseness
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55
Loading
update list of f(0)=1 answers, and update byte savings of prime power regex switch
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55
Loading
-5 bytes, but remove RegexMathEngine harness because this regex exposed a bug in it
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55
Loading
add some prose about what makes this output method interesting when applied to this problem
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55
Loading
add RegexMathEngine test harness
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55
Loading
be more specific about the difference between the two prime powers regexes
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55
Loading
add list of answers that give f(0)=1, and a minor edit
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55
Loading
update comments for 59 byte version
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55
Loading
added 2 characters in body
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55
Loading
-1 byte, adding built-in correct handling for an input of zero
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55
Loading
better wording
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55
Loading
Source Link
Deadcode
  • 12.9k
  • 2
  • 71
  • 55
Loading

AltStyle γ«γ‚ˆγ£γ¦ε€‰ζ›γ•γ‚ŒγŸγƒšγƒΌγ‚Έ (->γ‚ͺγƒͺγ‚ΈγƒŠγƒ«) /