10
\$\begingroup\$

Task:

Your task is make a program to check if there exists integers \$a \ge 2, b \ge 2\$ such that \$a^b=i\$ where \$i\$ is the input integer at least 2.

The catch is that your program must return a truthy value when its bytecode is translated to its integer representation (by default, base-10), in a reasonable time or not. To avoid trivial programs, the program value in decimal must be at least 65536 and also it must be irreducible (that is, removing any subset of characters fails to properly check if a number is a power). Also, the truthy and falsy values must be consistent.

Example:

For example, this program bytecode:

3D 09

This program is valid (without minimum value restriction) because it's a power: 3D0916 = 1562510 = 56.

Encoding notes:

The default encodings are the language's SBCS or UTF-8. If you use another encoding, specify it. For encodings with weird bases, that base is calculated. For example, in base-95, you would use base 95 to represent the program value.

Test cases:

True

4 8 9 16 25 27 128 144 625 1000 3125 15625 65536 90438207500880449001

False

3 5 6 10 28 68 101 233 999 1357 1400 65535 98989 89524690253396808102

Goal:

This is code golf, shortest valid program in bytes wins with tiebreaker being the program value.

Improve this question
\$\endgroup\$
11
  • \$\begingroup\$ What does "in a reasonable time" mean? This is not a speed challenge, so why this restriction? \$\endgroup\$ Commented Sep 22 at 14:14
  • 1
    \$\begingroup\$ You can eliminate clever solutions that are small yet slow. \$\endgroup\$ Commented Sep 22 at 14:28
  • 6
    \$\begingroup\$ If you use ASCII then your program will need to end in one of <spc>!#$%'()+-/135789;=?@ACDEGHIKMOQSUWXY[]_`acdeghikmoqsuwxy{} to stand a chance of being an exact power. \$\endgroup\$ Commented Sep 22 at 16:46
  • 1
    \$\begingroup\$ @JonathanAllan Fixed \$\endgroup\$ Commented Sep 22 at 17:02
  • 1
    \$\begingroup\$ ^(.+)((\1(.+))(?=(\3*)\1*$)\3*(?=\4$\5))+.$ is a regex that only matches perfect powers in unary but I doubt I can fulfil the perfect power requirement of the source. \$\endgroup\$ Commented Sep 27 at 10:11

2 Answers 2

Reset to default
10
\$\begingroup\$

Pyth, 29 27 bytes (thanks CursorCoercer)

iFhMrPQssm.6"}ÉoÌ ¦¼ø

Hexdump:

00000000: 6946 684d 7250 5173 736d 2e36 227d 1b82 iFhMrPQssm.6"}.. 00000010: c96f cc20 a619 8b99 bcf8 10 .o. .......

Outputs a number >1 for true, 1 for false.

Try it online! - The given input is the program value.

Explanation

This answer cheeses the challenge by using the length of an arbitrary string inside a computation. The string's contents can be varied to search for valid program values. I'm guessing the intent was to disallow putting arbitrary characters inside of a comment, but the challenge seems impossible without some cheese.

Start with the following Pyth program: iFhMrPQ8

 PQ - Prime factors of the input, e.g. 36 => [2, 2, 3, 3] r 8 - Run-length encoding, e.g. => [[2, 2], [2, 3]] hM - Take the first element of each element, e.g. => [2, 2] iF - Reduce with GCD

Notice that 8 is used as an "opcode" input to the r instruction - passing values other than 8 results in a different operation. This is important for the irreducibility requirement.

Replace 8 with the following snippet:

 "xxxxxxxxxxxxxx - 14 arbitrary characters in a string m.6 - Map each element to 0.6 s - Sum elements s - Convert to int

This is to satisfy the irreducibility requirement: if any part of the string is removed, the length no longer evaluates to 8. If any part of the length-computing code is removed, it also no longer evaluates to 8. It is unlikely that some subset of this string is valid Pyth code evaluating to 8 (i.e. if the string delimiter " is removed).

Then I just used a script to exhaustively check for perfect square program values. I also checked if I could reduce the size of the string literal (for example, by replacing .5 with .6), but no valid programs were found. .6 (and thus a string literal of length 14) is possible with non-printable characters in the string.

The program value is

43307635010343855810373044925567686241308005777350905277347330064

which is the square of

208104865417279121841411971317508

As a bonus, the program is fast enough for it to evaluate its program value in a reasonable time.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Whoops, I forgot to add a rule that says that the truthy and falsy values must be consistent. But still, good answer. +1 \$\endgroup\$ Commented Sep 25 at 0:22
  • \$\begingroup\$ 27 bytes A minor optimization to what you've done here. I kept thinking there were lots of bytes to save from this answer but keeping it irreducible is way harder than I anticipated. \$\endgroup\$ Commented Sep 25 at 22:18
  • 1
    \$\begingroup\$ @CursorCoercer Nice, I had set the script to avoid non-printables out of fear of some nebulous encoding issues, but it doesn't seem to be a problem. I'll update the answer. \$\endgroup\$ Commented Sep 25 at 22:33
  • \$\begingroup\$ Yeah Pyth can be fiddly about that sometimes, but it doesn't seem to be a problem here. I have managed to get it down to 24 bytes now. There might be another byte or two to be saved but this definitely feels much better \$\endgroup\$ Commented Sep 26 at 21:09
2
\$\begingroup\$

Jelly, 26 bytes

Lœ?“EgÆ/”vð@“N6XU¥⁴"EɠẒḌḂż

A full program that prints the maximal exponent to stdout, i.e. an integer greater than \$1\$ if a perfect power or \$1\$ if not.

Try it online! - way too slow for its own input (which is no longer a requirement).

Or see the test-suite.

The bytecode is:

4C 1E 3F FE 45 67 0D 2F FF 76 18 40 FE 4E 36 58 55 04 84 22 45 9F BD AD BF F9

which, as base 10 is (TIO)

$$122317173525583340303786060012597342485674060763941233767596025$$ $$ = (5 \cdot 19 \cdot 254279 \cdot 457835662419192582175421)^{2}$$

How?

Lœ?“EgÆ/”vð@“... - Main Link: integer, N > 1 “... - length 13 string -> S ð@ - dyadic chain - f(S, N)... “EgÆ/” - "EgÆ/" œ? - permutation of {that} at lexicographic index... L - ...length of {S} -> "ÆEg/" v - evaluate as Jelly code with {N} as the left argument i.e: ÆE - prime factor exponents (e.g. 500 = 2*2*5*5*5 -> [2,0,3]) / - reduce by: g - greatest common divisor

If the output really needs to be truthy in our language and falsey otherwise, this, at \$28\$ bytes, prints a non-zero number if a perfect power (truthy) or zero if not (falsey):

Lœ?“ÆgCE/”vɓ@“F6Æ_æṃcSḌɠ2ḌƈÑ

The C produces one minus its argument, and the string is now length fourteen.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Impressive, but does this observe "must be irreducible"? \$\endgroup\$ Commented Sep 22 at 21:46
  • \$\begingroup\$ @doubleunary err no, missed that this was meant to be totally radiation hardened! \$\endgroup\$ Commented Sep 22 at 22:22
  • 1
    \$\begingroup\$ @doubleunary I should also have said thanks for letting me know! Now the code is irreducible. \$\endgroup\$ Commented Sep 26 at 21:38

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.