Regex (ECMAScript), 70 68 56 52 bytes
-4 bytes by successfully combining base \$2\$ and \$10\$ into a single expression, as was already accomplished in the other versions
^((x)|(x))((((\2*)\3*)(\2\7){8}x(?=\6$))*x){2}\2{8}$
Try it online!
Takes its input in unary, as a sequence of x characters whose length represents the number.
Here are some examples of how this 52 byte version works:
Example input: 1001000
Choose base 10 and subtract 1 from tail
1000999
Iteration 1 of the outer loop:
1000999
100099
10009
1000
tail -= 1
999
Iteration 2 of the outer loop:
999
99
9
tail -= 1
8
Assert tail == 10 - 2
Example input: 11
Choose base 10 and subtract 1 from tail
10
Iteration 1 of the outer loop:
10
tail -= 1
9
Iteration 2 of the outer loop:
9
tail -= 1
8
Assert tail == 10 - 2
The regex, pretty-printed and commented:
^ # tail = N = input number
# Pick which base to operate in, and tail -= 1
(
(x) # \2 = 1 or unset (unset=0 due to ECMAScript NPCG behavior); B=10
|
(x) # \3 = 1 or unset (unset=0 due to ECMAScript NPCG behavior); B=2
)
# Assert tail is the sum of two powers of B
(
(
# tail = (tail + 1) / B - 1
((\2*)\3*) # if \2=1, then \6 = \7 = (tail + 1) / 10 - 1;
# if \3=1, then \6 = (tail + 1) / 2 - 1, and \7 = 0
(\2\7){8}
x
(?=\6$)
)* # Loop the above zero or more times
x # tail -= 1
){2} # Loop the above exactly twice
\2{8}$ # Assert tail == B - 2
The following text applies to the earlier 56 byte version:
This turned out to be very similar to Neil's 58 byte regex. I looked at the byte count, but not at the regex itself, in that answer's heading before working on the problem myself. It took me a while to figure out how to make a non-ECMAScript-specific regex shorter than 70 bytes. The hangup for me was, that I was doing it like this:
^((((x+)\4{8}(?=\4$))*x(?=(xx)*$)){2}|(((x+)(?=\8$))*x(?=(xx)*$)){2})$
In order to prevent the loop from subtracting the same power of 2 or 10 twice (and matching, for example, 512 and 200) I had to use (?=(xx)*$) to assert that tail is even after subtracting 1 (this works for both 2 and 10, as they are both even). Finally I figured out that I could just use two alternatives inside the (...){2} loop, one that must do at least one division before subtracting 1, and one that can only subtract 1 if it's the first thing done, and this saved 7 bytes per base, giving 70 - 2×7 = 56 bytes:
^((((x+)\4{8}(?=\4$))+x|^x){2}|(((x+)(?=\7$))+x|^x){2})$
Regex (ECMAScript / Perl / PCRE / Java / Boost / Python / .NET), 54 bytes
^(x?)(^x|\B)((((\1*)\2*)(\1\6){8}x(?=\5$))*x){2}\1{8}$
This is a port of the 52 byte ECMAScript version to be NPCG-behavior-independent and compatible with a wide variety of regex engines including ECMAScript (i.e., "generic"). This is done by changing ((x)|(x)) (where \2 and \3 are differently 1 or unset) to (x?)(^x|\B) (where \1 and \2 are differently 1 or 0).
Try it online! - ECMAScript
Try it online! - Perl
Try it online! - PCRE
Try it online! - Java
Try it online! - Boost (throws some errors, but this is fixed in later versions than what is on TIO)
Try it online! - Python
Attempt This Online! - Python (import regex)
Try it online! - .NET
It exposes a bug in the regex engine used by Ruby. The 56 byte regex works in Ruby: Try it online!
But the 54 byte regex does not: Try it online! Boiling this down, it appears that ^((x*)(){4}(?=\2$))*x$ matches powers of 2 just fine, but ^((x*)(){5}(?=\2$))*x$ does not.
Similarly, while it works with Python's re module (see above), it exposed a bug in the the more powerful regex module: Try it online! [This bug has now been fixed!]
It also exposes a bug in older versions of Boost, as stated above – throwing an error on 480, 512, 584, and many other larger numbers. In older versions of Notepad++ (using the older Boost versions), this is treated as a match.
Regex (ECMAScript+(?*) / PCRE2 v10.35+), 54 47 bytes
^(?*(x)|(x))((((\1*)\2*)\6{8}(?=\5$))+x|^x){2}$
Attempt This Online! - PCRE2
In this version, the two bases \$10\$ and \$2\$ are combined, by choosing between them using the initial (x)|(x). Thanks to molecular lookbehind (?*), this can be done without subtracting 1 from the number being tested:
^
(?*
(x) # \2 = 1 or unset (unset=0 due to ECMAScript NPCG behavior); B=10
|
(x) # \3 = 1 - \2; B=2
)
# Assert tail is the sum of two powers of B
(
# Alternative #1: Divide evenly by B as many times as possible, at least once
# (meaning tail has to be initially divisible by B), then subtract 1.
(
((\1*)\2*)\6{8}(?=\5$) # assert tail % B == 0; tail /= B
)+
x # tail -= 1
|
# Alternative #2: Don't divide at all, and just subtract 1, but only if this is
# the first thing we do. If this path is taken, only alternative #1 can next.
^x # assert tail == N; tail -= 1
){2} # Loop the above exactly twice
$ # Assert tail == 0
When \1=1 and \2=0, ((\1*)\2*)\6{8}(?=\5$) behaves like (x*)\5{8}(?=\5$), dividing by \$10\$.
When \1=0 and \2=1, ((\1*)\2*)\6{8}(?=\5$) behaves like (x*)(?=\5$), dividing by \$2\$.
Regex (ECMAScript 2018 / Pythonregex / .NET), 51 bytes
((x)|(x))$(?<=^(x((?<=^\6)\7{8}(\3*(\2*)))+|x$){2})
Try it online! - ECMAScript 2018 (Node v11.6.0, with bug workaround)
Attempt This Online! - ECMAScript 2018 (Node v17.3.0+, bug fixed)
Attempt This Online! - Python import regex
Try it online! - .NET
This is a port of the ECMAScript+(?*) version to variable-length right-to-left-evaluated positive lookbehind (?<=). It starts 1 off from the end, reaches the end by capturing a determination of whether to work in base \$10\$ or \$2\$, then does the rest of its work going backwards.
It exposed a bug present in the ECMAScript 2018 regex engine of both SpiderMonkey (Firefox) and V8 (Chrome / Node). To make this regex work, the multiline flag must be enabled. It fails to work without the flag. pxeger has reported the bug. It was since then fixed.
(
(x) # \2 = 1 or unset (unset=0 due to ECMAScript NPCG behavior); B=10
|
(x) # \3 = 1 - \2; B=2
)
$ # head = N = input number
# Assert head is the sum of two powers of B
(?<= # Lookbehind - evaluated right-to-left
^ # Assert head == 0
(
# Alternative #1: Divide evenly by B as many times as possible, at least once
# (meaning head has to be initially divisible by B), then subtract 1.
x # head -= 1
(
(?<=^\6)\7{8}(\3*(\2*)) # assert head % B == 0; head /= B
)+
|
# Alternative #2: Don't divide at all, and just subtract 1, but only if this is
# the first thing we do. If this path is taken, only alternative #1 can next.
x$ # assert head == N; head -= 1
){2} # Loop the above exactly twice
)
Regex (Perl / PCRE / Boost / Python / Ruby / .NET), 51 39 bytes
^()?(((x*)(?(1)\4{8})(?=\4$))+x|^x){2}$
Try it online! - Perl
Try it online! - PCRE
Try it online! - Boost
Try it online! - Python
Attempt This Online! - Python (import regex)
Try it online! - Ruby
Try it online! - .NET
This version takes advantage of a conditional group (?(1)\4{8}) to determine whether to work in base \$10\$ or \$2\$.
^
()? # \1 = choose between B=10 (if set) or B=2 (if unset)
# Assert tail is the sum of two powers of B
(
# Alternative #1: Divide evenly by B as many times as possible, at least once
# (meaning tail has to be initially divisible by B), then subtract 1.
(
(x*)(?(1)\4{8})(?=\4$) # assert tail % B == 0; tail /= B
)+
x # tail -= 1
|
# Alternative #2: Don't divide at all, and just subtract 1, but only if this is
# the first thing we do. If this path is taken, only alternative #1 can next.
^x # assert tail == N; tail -= 1
){2} # Loop the above exactly twice
$ # Assert tail == 0
Regex (Perl / PCRE / Java / Boost / Python / Ruby / .NET), 44 bytes
^()?(((x*)(\1\4{8}|(?!\1))(?=\4$))+x|^x){2}$
Try it online! - Java / Perl / PCRE / Boost / Python / Ruby / .NET
^(()|())(((x*)(\2\6{8}|\3)(?=\6$))+x|^x){2}$
Try it online! - Java / Perl / PCRE / Boost / Python / Ruby / .NET
These are ports of the 39 byte version, to a regex flavor that has no conditionals. In the first one, the (?(1)\4{8}) conditional is replaced with (\1\4{8}|(?!\1)) which behaves equivalently at a cost of 5 extra bytes. In the second the expression (()|()) instead of ()? is used to determine the mode (which either sets \2 or \3 leaving the other one unset), and the conditional is replaced with (\2\6{8}|\3). The regex is otherwise unchanged (except for shifting the capture group numbering).
10^x+10^y = 2^x+2^bto5^x = 2^b/10^y? It looks like you may have incorrectly treated the former expression as though it said*instead of+, and then divided both sides by2^x*10^y. \$\endgroup\$Input will always be an integer, but it may not always be positive.How are negative numbers encoded? With a minus in front? With a 1 in front? Using two's complement? \$\endgroup\$-11as an example (again would be with a minus sign). I can only imagine that your rule is to convert to a base representation using digits in \$[-b+1..0]\$ e.g. -123 base 10 is[-1,-2,-3]\$= -1 \times 10^2 + -2 \times 10^1 + -1 \times 10^0\$. Without a spec it seems we can say all negative numbers are not Two Bit Numbers, so why, are there example ones and why do we even need to handle them? \$\endgroup\$