Reciprocal copycats
up vote
17
down vote
favorite
Let $A$ be a positive integer consisting of $n$ decimal digits $d_1,d_2,...,d_n$. Let $B$ be another positive integer.
For the purpose of this challenge, we call $A$ a copycat of $B$ if there exists at least one list of positive integers $p_1,p_2,...,p_n$ such that:
$$sum_{i=1}^{n}{{d_i}^{p_i}}=B$$
$A$ and $B$ are called reciprocal copycats if $A$ is a copycat of $B$ and $B$ is a copycat of $A$.
Example
$526$ and $853$ are reciprocal copycats because:
$$5^3 + 2^9 + 6^3 = 853$$
and:
$$8^3 + 5^1 + 3^2 = 526$$
The challenge
Given two positive integers $A$ and $B$, your task is to print or return a truthy value if $A$ and $B$ are reciprocal copycats or a falsy value otherwise.
Clarifications and rules
- You may take $A$ and $B$ in any reasonable, unambiguous format (e.g. integers, strings, lists of digits, ...)
$A$ and $B$ may be equal. If a number is a reciprocal copycat of itself, it belongs to A007532.- Instead of truthy/falsy values, you may return two distinct consistent values.
- For $1le A<1000$ and $1le B<1000$, your code must complete in less than one minute. If it's taking too much time for higher values, it must however be able to solve them in theory.
- This is code-golf.
Test cases
Truthy:
1 1
12 33
22 64
8 512
23 737
89 89
222 592
526 853
946 961
7 2401
24 4224
3263 9734
86 79424
68995 59227
32028 695345
Falsy:
1 2
3 27
9 24
24 42
33 715
33 732
222 542
935 994
17 2401
8245 4153
code-golf decision-problem integer
asked Nov 13 at 10:36
Arnauld
70.1k686295
add a comment |
up vote
17
down vote
favorite
Let $A$ be a positive integer consisting of $n$ decimal digits $d_1,d_2,...,d_n$. Let $B$ be another positive integer.
For the purpose of this challenge, we call $A$ a copycat of $B$ if there exists at least one list of positive integers $p_1,p_2,...,p_n$ such that:
$$sum_{i=1}^{n}{{d_i}^{p_i}}=B$$
$A$ and $B$ are called reciprocal copycats if $A$ is a copycat of $B$ and $B$ is a copycat of $A$.
Example
$526$ and $853$ are reciprocal copycats because:
$$5^3 + 2^9 + 6^3 = 853$$
and:
$$8^3 + 5^1 + 3^2 = 526$$
The challenge
Given two positive integers $A$ and $B$, your task is to print or return a truthy value if $A$ and $B$ are reciprocal copycats or a falsy value otherwise.
Clarifications and rules
- You may take $A$ and $B$ in any reasonable, unambiguous format (e.g. integers, strings, lists of digits, ...)
$A$ and $B$ may be equal. If a number is a reciprocal copycat of itself, it belongs to A007532.- Instead of truthy/falsy values, you may return two distinct consistent values.
- For $1le A<1000$ and $1le B<1000$, your code must complete in less than one minute. If it's taking too much time for higher values, it must however be able to solve them in theory.
- This is code-golf.
Test cases
Truthy:
1 1
12 33
22 64
8 512
23 737
89 89
222 592
526 853
946 961
7 2401
24 4224
3263 9734
86 79424
68995 59227
32028 695345
Falsy:
1 2
3 27
9 24
24 42
33 715
33 732
222 542
935 994
17 2401
8245 4153
code-golf decision-problem integer
asked Nov 13 at 10:36
Arnauld
70.1k686295
Suggested case:17 2401 -> false. I'm almost tripped on this.
– Shieru Asakoto
Nov 15 at 5:46
add a comment |
up vote
17
down vote
favorite
up vote
17
down vote
favorite
Let $A$ be a positive integer consisting of $n$ decimal digits $d_1,d_2,...,d_n$. Let $B$ be another positive integer.
For the purpose of this challenge, we call $A$ a copycat of $B$ if there exists at least one list of positive integers $p_1,p_2,...,p_n$ such that:
$$sum_{i=1}^{n}{{d_i}^{p_i}}=B$$
$A$ and $B$ are called reciprocal copycats if $A$ is a copycat of $B$ and $B$ is a copycat of $A$.
Example
$526$ and $853$ are reciprocal copycats because:
$$5^3 + 2^9 + 6^3 = 853$$
and:
$$8^3 + 5^1 + 3^2 = 526$$
The challenge
Given two positive integers $A$ and $B$, your task is to print or return a truthy value if $A$ and $B$ are reciprocal copycats or a falsy value otherwise.
Clarifications and rules
- You may take $A$ and $B$ in any reasonable, unambiguous format (e.g. integers, strings, lists of digits, ...)
$A$ and $B$ may be equal. If a number is a reciprocal copycat of itself, it belongs to A007532.- Instead of truthy/falsy values, you may return two distinct consistent values.
- For $1le A<1000$ and $1le B<1000$, your code must complete in less than one minute. If it's taking too much time for higher values, it must however be able to solve them in theory.
- This is code-golf.
Test cases
Truthy:
1 1
12 33
22 64
8 512
23 737
89 89
222 592
526 853
946 961
7 2401
24 4224
3263 9734
86 79424
68995 59227
32028 695345
Falsy:
1 2
3 27
9 24
24 42
33 715
33 732
222 542
935 994
17 2401
8245 4153
code-golf decision-problem integer
asked Nov 13 at 10:36
Arnauld
70.1k686295
Let $A$ be a positive integer consisting of $n$ decimal digits $d_1,d_2,...,d_n$. Let $B$ be another positive integer.
For the purpose of this challenge, we call $A$ a copycat of $B$ if there exists at least one list of positive integers $p_1,p_2,...,p_n$ such that:
$$sum_{i=1}^{n}{{d_i}^{p_i}}=B$$
$A$ and $B$ are called reciprocal copycats if $A$ is a copycat of $B$ and $B$ is a copycat of $A$.
Example
$526$ and $853$ are reciprocal copycats because:
$$5^3 + 2^9 + 6^3 = 853$$
and:
$$8^3 + 5^1 + 3^2 = 526$$
The challenge
Given two positive integers $A$ and $B$, your task is to print or return a truthy value if $A$ and $B$ are reciprocal copycats or a falsy value otherwise.
Clarifications and rules
- You may take $A$ and $B$ in any reasonable, unambiguous format (e.g. integers, strings, lists of digits, ...)
$A$ and $B$ may be equal. If a number is a reciprocal copycat of itself, it belongs to A007532.- Instead of truthy/falsy values, you may return two distinct consistent values.
- For $1le A<1000$ and $1le B<1000$, your code must complete in less than one minute. If it's taking too much time for higher values, it must however be able to solve them in theory.
- This is code-golf.
Test cases
Truthy:
1 1
12 33
22 64
8 512
23 737
89 89
222 592
526 853
946 961
7 2401
24 4224
3263 9734
86 79424
68995 59227
32028 695345
Falsy:
1 2
3 27
9 24
24 42
33 715
33 732
222 542
935 994
17 2401
8245 4153
code-golf decision-problem integer
code-golf decision-problem integer
asked Nov 13 at 10:36
Arnauld
70.1k686295
asked Nov 13 at 10:36
Arnauld
70.1k686295
edited Nov 15 at 11:20
asked Nov 13 at 10:36
Arnauld
70.1k686295
asked Nov 13 at 10:36
Arnauld
70.1k686295
asked Nov 13 at 10:36
Arnauld
70.1k686295
70.1k686295
Suggested case:17 2401 -> false. I'm almost tripped on this.
– Shieru Asakoto
Nov 15 at 5:46
add a comment |
Suggested case:17 2401 -> false. I'm almost tripped on this.
– Shieru Asakoto
Nov 15 at 5:46
Suggested case:
17 2401 -> false. I'm almost tripped on this.– Shieru Asakoto
Nov 15 at 5:46
Suggested case:
17 2401 -> false. I'm almost tripped on this.– Shieru Asakoto
Nov 15 at 5:46
add a comment |
10 Answers
10
active
oldest
votes
up vote
8
down vote
Brachylog, 19 bytes
ẹ{∧ℕ₁;?↔^}ᵐ².+ᵐ↔?∧≜
Try it online!
Outputs true. or false.
Explanation
ẹ Split the numbers into lists of digits
{ }ᵐ² For each digit
∧ℕ₁ Let I be a strictly positive integer
;?↔^ Compute the digit to the power I (which is unknown currently)
. Call . the list of those new numbers
.+ᵐ Their mapped sum results…
↔? …in the reverse of the input
∧≜ Find if there effectively are values for the numbers in . to satisfy
these relationships
answered Nov 13 at 10:52
Fatalize
26.8k448134
2
@Arnauld Fixed at the cost of 1 byte. It failed because2401contained a0which didn't work with the way I checked thatIwas strictly positive (because I mapped it on bothIand the digit to save bytes)
– Fatalize
Nov 13 at 12:42
add a comment |
up vote
6
down vote
Husk, 17 bytes
Λλ€⁰mΣΠTṪ^ḣ√⁰d)De
Try it online!
Finishes all test cases under 1000 in about 11 seconds.
Explanation
Λλ€⁰mΣΠTṪ^ḣ√⁰d)De Implicit inputs, say 12 and 33.
e Put into a list: [12,33]
D Duplicate: [12,33,12,33]
Λ Does this hold for all adjacent pairs:
(12,33 is checked twice but it doesn't matter)
For example, arguments are 33 and 12.
λ ) Anonymous function with arguments 33 (explicit) and 12 (implicit).
d Base-10 digits of implicit argument: [1,2]
ḣ√⁰ Range to square root of explicit argument: [1,2,3,4]
Ṫ^ Outer product with power: [[1,2],[1,4],[1,8],[1,16],[1,32]]
T Transpose: [[1,1,1,1,1],[2,4,8,16,32]]
Π Cartesian product: [[1,2],[1,4],...,[1,32]]
mΣ Map sum: [3,5,...,33]
€⁰ Is the explicit argument in this list? Yes.
Why it works
If we have $B = d_1^{p_1} + cdots + d_n^{p_n}$ where the $d_i$ are digits and $p_i$ are positive integers, then $d_i^{p_i} leq B$ for all $i$, or equivalently $p_i leq log_{d_i} B$.
We can ignore the case $d_i leq 1$, since exponentiating $0$ or $1$ does not change it.
In my program the search space is $1 leq p_i leq sqrt{B}$ (to comply with the time restriction; I would use $1 leq p_i leq B$ otherwise), so if we have $lfloor log_{d_i} B rfloor leq lfloor sqrt{B} rfloor$, then everything is fine.
If $d_i geq 3$, this holds for all natural numbers $B$, so the only dangerous case is $d_i = 2$.
We have $lfloor log_2 B rfloor > lfloor sqrt{B} rfloor$ only for $B = 8$.
In this case $2^3 = 8$, but the search only considers exponents $1$ and $2$.
If the other number number $A$ contains the digit $2$, either it has other nonzero digits as well (so the exponent of $2$ cannot be $3$ in the sum), or $A = 2 cdot 10^k$ for some $k$.
In the latter case, $A$ is not a power of $8$, so it cannot be a copycat of $B$ anyway, and the program correctly returns a falsy value regardless of the other computation.
answered Nov 13 at 20:23
Zgarb
26.3k461228
Great answer which makes me want to learn Husk. Two questions: 1. the implicit argument is mentioned again after you introduce it. When is it used? 2. Could you elaborate on why this algorithm is equivalent to the one posed in the OP?
– Jonah
Nov 15 at 4:28
1
@Jonah 1. The digit functiondtakes the implicit argument. I clarified this in the explanation. 2. I added an argument for the program's correctness.
– Zgarb
Nov 15 at 11:55
Thank you... btw, the part that had confused me was "where does the list of all ones come from?".... rereading i now realize this is merely because all the powers of 1 are just one....
– Jonah
Nov 15 at 18:30
add a comment |
up vote
4
down vote
Python 2, 102 bytes
lambda a,b:g(a,b)*g(b,a)
g=lambda a,b,e=1:b==a<1or(b>0<=b-e>=0<a)and(g(a/10,b-(a%10)**e)or g(a,b,e+1))
Try it online!
answered Nov 13 at 13:23
ovs
18.3k21059
add a comment |
up vote
4
down vote
05AB1E, 26 22 bytes
εVтLIàgãεYSym}OIyKå}˜P
Takes the input as a list (i.e. [526,853]).
Try it online or verify most test cases in the range [1,999].
Similar as my old answer below, except that the [1,n] list is hardcoded to [1,100], and it creates the cartesian list twice, once for each input-mapping, which is the main bottleneck in terms of performance.
Old 26 bytes answer that's better for performance:
Z©bgL®gãUεVXεYSym}OsN>èå}P
In this version I traded in some bytes to make the performance a lot better so it can run [1,1000] with ease. Test cases containing numbers in the range [1,9999] are done in about a second on TIO. Test cases in the range [10000,99999] in about 10-15 seconds on TIO. Above that it will timeout.
Try it online or verify all test cases with numbers in the range [1,9999].
Explanation:
Z # Push the max of the (implicit) input-list (without popping)
# i.e. [526,853] → 853
© # Store it in the register (without popping)
b # Convert to binary
# i.e. 853 → 1101010101
g # Take its length
# i.e. 1101010101 → 10
L # Pop and push a list [1, n]
# i.e. 10 → [1,2,3,4,5,6,7,8,9,10]
® # Push the max from the register
g # Take its length
# i.e. 853 → 3
ã # Cartesian product the list that many times
# i.e. [1,2,3,4,5,6,7,8,9,10] and 3
# → [[1,1,1],[1,1,2],[1,1,3],...,[10,10,8],[10,10,9],[10,10,10]]
U # Pop and store it in variable `X`
ε } # Map both values of the input list:
V # Store the current value in variable `Y`
Xε } # Map `y` over the numbers of variable `X`
Y # Push variable `Y`
S # Convert it to a list of digits
# i.e. 526 → [5,2,6]
ym # Take each digit to the power of the current cartesian product sublist
# i.e. [5,2,6] and [3,9,3] → [125,512,216]
O # Take the sum of each inner list
# i.e. [[5,2,6],[5,2,36],[5,2,216],...,[125,512,216],...]
# → [13,43,223,...,853,...]
s # Swap to push the (implicit) input
N> # Push the index + 1
# i.e. 0 → 1
è # Index into the input-list (with automatic wraparound)
# i.e. [526,853] and 1 → 853
å # Check if it's in the list of sums
# i.e. [13,43,223,...,853,...] and 853 → 1
P # Check if it's truthy for both both (and output implicitly)
# i.e. [1,1] → 1
answered Nov 13 at 13:15
Kevin Cruijssen
34.5k554182
add a comment |
up vote
4
down vote
Haskell, 77 bytes
a#b=a!b&&b!a
a!b|a<1=b==0|b<1=b>1|1<2=or[div a 10!(b-mod a 10^e)|e<-[1..b+1]]
Try it online!
answered Nov 13 at 13:39
ovs
18.3k21059
add a comment |
up vote
4
down vote
Perl 6, 87 84 69 bytes
-15 bytes thanks to nwellnhof!
{!grep {!grep $^b,[X+] 0,|map (*X**1..$b.msb+1),$^a.comb},.[0,1,1,0]}
Try it online!
Anonymous code block that returns True or False.
Explanation:
{!grep {!grep $^b,[X+] 0,|map (*X**1..$b.msb+1),$^a.comb},.[0,1,1,0]}
{ } # Anonymous code block
!grep # None of:
.[0,1,1,0] # The input and the input reverse
{!grep # None of
[X+] # All possible sums of
0,| # 0 (this is to prevent single digit numbers being crossed with themself)
map ,$^a.comb # Each digit mapped to
(*X** ) # The power of
1..$b.msb+1 # All of 1 to the most significant bit of b plus 1
# This could just be b+1, but time constraints...
$^b, # Is equal to b
answered Nov 13 at 11:20
Jo King
19.7k245103
@Arnauld, A Junction is Truthy/Falsey, as I've shown by using the boolify operator before outputting. I golfed it to something else anyway, though I could save a byte if I could output a truthy value for false and vice-versa...?
– Jo King
Nov 13 at 11:40
Thanks for the clarification. About the truthy/falsy inversion: I'd rather say no.
– Arnauld
Nov 13 at 11:45
add a comment |
up vote
4
down vote
JavaScript (Node.js), 116 92 89 86 83 77 bytes
a=>b=>(G=(c,g,f=h=g%10)=>g?c>f&f>1&&G(c,g,h*f)||G(c-f,g/10|0):!c)(a,b)&G(b,a)
Try it online!
Expect input as (A)(B).
answered Nov 13 at 11:34
Shieru Asakoto
2,370314
Strings are fine. (I've clarified the input format in the challenge.)
– Arnauld
Nov 13 at 11:41
@Arnauld Oh I've just found a method not using string but also 108 bytes.
– Shieru Asakoto
Nov 13 at 11:48
add a comment |
up vote
2
down vote
J, 56 bytes
h~*h=.4 :'x e.+/|:>,{x 4 :''<y&*^:(x&>)^:a:y''"+"."+":y'
Try it online!
Yay, nested explicit definition!
How it works
powers =. 4 :'<y&*^:(x&>)^:a:y' Explicit aux verb. x = target, y = digit
y Starting from y,
y&*^: ^:a: collect all results of multiplying y
(x&>) until the result is at least x
< Box it.
h=.4 :'x e.+/|:>,{x powers"+"."+":y' Explicit aux verb. x, y = two input numbers
"."+":y Digits of y
x powers"+ Collect powers of digits of y under x
{ Cartesian product of each item
+/|:>, Format correctly and compute the sums
x e. Does x appear in the list of sums?
h~*h Tacit main verb. x, y = two input numbers
Since h tests the condition in only one direction,
test again the other way around (~) and take the AND.
answered Nov 16 at 0:31
Bubbler
6,044759
add a comment |
up vote
1
down vote
Python 2, 149 147 143 139 132 118 108 107 106 105 bytes
lambda a,b:g(a,b)*g(b,a)
g=lambda a,b:any(g(a/10,b-(a%10)**-~i)for i in(a*b>0)*range(len(bin(b))))or b==0
Try it online!
-4 bytes, thanks to Vedant Kandoi
answered Nov 13 at 11:32
TFeld
13.7k21239
>0can be removed.not a:a<1.b==0:b<1
– Vedant Kandoi
Nov 13 at 11:37
@VedantKandoi Thanks, thoughb<0doesn't work
– TFeld
Nov 13 at 11:41
add a comment |
up vote
1
down vote
J, 68 bytes
I thought J would perform quite well here, but it ended up being tougher than I expected and would love any suggestions for further golfing...
g=.#@#:@[
1 1-:[:(([:+./[=1#.]^"#.1+g#.inv[:i.g^#@])"."0@":)/"1],:|.
Try it online!
NOTE: we subtract 3 chars from the TIO count there since f=. on the main function doesn't count
ungolfed
1 1 -: [: (([: +./ [ = 1 #. ] ^"#. 1 + g #.inv [: i. g ^ #@]) "."0@":)/"1 ] ,: |.
answered Nov 15 at 3:49
Jonah
1,981816
add a comment |
10 Answers
10
active
oldest
votes
10 Answers
10
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
8
down vote
Brachylog, 19 bytes
ẹ{∧ℕ₁;?↔^}ᵐ².+ᵐ↔?∧≜
Try it online!
Outputs true. or false.
Explanation
ẹ Split the numbers into lists of digits
{ }ᵐ² For each digit
∧ℕ₁ Let I be a strictly positive integer
;?↔^ Compute the digit to the power I (which is unknown currently)
. Call . the list of those new numbers
.+ᵐ Their mapped sum results…
↔? …in the reverse of the input
∧≜ Find if there effectively are values for the numbers in . to satisfy
these relationships
answered Nov 13 at 10:52
Fatalize
26.8k448134
2
@Arnauld Fixed at the cost of 1 byte. It failed because2401contained a0which didn't work with the way I checked thatIwas strictly positive (because I mapped it on bothIand the digit to save bytes)
– Fatalize
Nov 13 at 12:42
add a comment |
up vote
8
down vote
Brachylog, 19 bytes
ẹ{∧ℕ₁;?↔^}ᵐ².+ᵐ↔?∧≜
Try it online!
Outputs true. or false.
Explanation
ẹ Split the numbers into lists of digits
{ }ᵐ² For each digit
∧ℕ₁ Let I be a strictly positive integer
;?↔^ Compute the digit to the power I (which is unknown currently)
. Call . the list of those new numbers
.+ᵐ Their mapped sum results…
↔? …in the reverse of the input
∧≜ Find if there effectively are values for the numbers in . to satisfy
these relationships
answered Nov 13 at 10:52
Fatalize
26.8k448134
2
@Arnauld Fixed at the cost of 1 byte. It failed because2401contained a0which didn't work with the way I checked thatIwas strictly positive (because I mapped it on bothIand the digit to save bytes)
– Fatalize
Nov 13 at 12:42
add a comment |
up vote
8
down vote
up vote
8
down vote
Brachylog, 19 bytes
ẹ{∧ℕ₁;?↔^}ᵐ².+ᵐ↔?∧≜
Try it online!
Outputs true. or false.
Explanation
ẹ Split the numbers into lists of digits
{ }ᵐ² For each digit
∧ℕ₁ Let I be a strictly positive integer
;?↔^ Compute the digit to the power I (which is unknown currently)
. Call . the list of those new numbers
.+ᵐ Their mapped sum results…
↔? …in the reverse of the input
∧≜ Find if there effectively are values for the numbers in . to satisfy
these relationships
answered Nov 13 at 10:52
Fatalize
26.8k448134
Brachylog, 19 bytes
ẹ{∧ℕ₁;?↔^}ᵐ².+ᵐ↔?∧≜
Try it online!
Outputs true. or false.
Explanation
ẹ Split the numbers into lists of digits
{ }ᵐ² For each digit
∧ℕ₁ Let I be a strictly positive integer
;?↔^ Compute the digit to the power I (which is unknown currently)
. Call . the list of those new numbers
.+ᵐ Their mapped sum results…
↔? …in the reverse of the input
∧≜ Find if there effectively are values for the numbers in . to satisfy
these relationships
answered Nov 13 at 10:52
Fatalize
26.8k448134
edited Nov 13 at 12:41
answered Nov 13 at 10:52
Fatalize
26.8k448134
answered Nov 13 at 10:52
Fatalize
26.8k448134
answered Nov 13 at 10:52
Fatalize
26.8k448134
26.8k448134
2
@Arnauld Fixed at the cost of 1 byte. It failed because2401contained a0which didn't work with the way I checked thatIwas strictly positive (because I mapped it on bothIand the digit to save bytes)
– Fatalize
Nov 13 at 12:42
add a comment |
2
@Arnauld Fixed at the cost of 1 byte. It failed because2401contained a0which didn't work with the way I checked thatIwas strictly positive (because I mapped it on bothIand the digit to save bytes)
– Fatalize
Nov 13 at 12:42
2
2
@Arnauld Fixed at the cost of 1 byte. It failed because
2401 contained a 0 which didn't work with the way I checked that I was strictly positive (because I mapped it on both I and the digit to save bytes)– Fatalize
Nov 13 at 12:42
@Arnauld Fixed at the cost of 1 byte. It failed because
2401 contained a 0 which didn't work with the way I checked that I was strictly positive (because I mapped it on both I and the digit to save bytes)– Fatalize
Nov 13 at 12:42
add a comment |
up vote
6
down vote
Husk, 17 bytes
Λλ€⁰mΣΠTṪ^ḣ√⁰d)De
Try it online!
Finishes all test cases under 1000 in about 11 seconds.
Explanation
Λλ€⁰mΣΠTṪ^ḣ√⁰d)De Implicit inputs, say 12 and 33.
e Put into a list: [12,33]
D Duplicate: [12,33,12,33]
Λ Does this hold for all adjacent pairs:
(12,33 is checked twice but it doesn't matter)
For example, arguments are 33 and 12.
λ ) Anonymous function with arguments 33 (explicit) and 12 (implicit).
d Base-10 digits of implicit argument: [1,2]
ḣ√⁰ Range to square root of explicit argument: [1,2,3,4]
Ṫ^ Outer product with power: [[1,2],[1,4],[1,8],[1,16],[1,32]]
T Transpose: [[1,1,1,1,1],[2,4,8,16,32]]
Π Cartesian product: [[1,2],[1,4],...,[1,32]]
mΣ Map sum: [3,5,...,33]
€⁰ Is the explicit argument in this list? Yes.
Why it works
If we have $B = d_1^{p_1} + cdots + d_n^{p_n}$ where the $d_i$ are digits and $p_i$ are positive integers, then $d_i^{p_i} leq B$ for all $i$, or equivalently $p_i leq log_{d_i} B$.
We can ignore the case $d_i leq 1$, since exponentiating $0$ or $1$ does not change it.
In my program the search space is $1 leq p_i leq sqrt{B}$ (to comply with the time restriction; I would use $1 leq p_i leq B$ otherwise), so if we have $lfloor log_{d_i} B rfloor leq lfloor sqrt{B} rfloor$, then everything is fine.
If $d_i geq 3$, this holds for all natural numbers $B$, so the only dangerous case is $d_i = 2$.
We have $lfloor log_2 B rfloor > lfloor sqrt{B} rfloor$ only for $B = 8$.
In this case $2^3 = 8$, but the search only considers exponents $1$ and $2$.
If the other number number $A$ contains the digit $2$, either it has other nonzero digits as well (so the exponent of $2$ cannot be $3$ in the sum), or $A = 2 cdot 10^k$ for some $k$.
In the latter case, $A$ is not a power of $8$, so it cannot be a copycat of $B$ anyway, and the program correctly returns a falsy value regardless of the other computation.
answered Nov 13 at 20:23
Zgarb
26.3k461228
Great answer which makes me want to learn Husk. Two questions: 1. the implicit argument is mentioned again after you introduce it. When is it used? 2. Could you elaborate on why this algorithm is equivalent to the one posed in the OP?
– Jonah
Nov 15 at 4:28
1
@Jonah 1. The digit functiondtakes the implicit argument. I clarified this in the explanation. 2. I added an argument for the program's correctness.
– Zgarb
Nov 15 at 11:55
Thank you... btw, the part that had confused me was "where does the list of all ones come from?".... rereading i now realize this is merely because all the powers of 1 are just one....
– Jonah
Nov 15 at 18:30
add a comment |
up vote
6
down vote
Husk, 17 bytes
Λλ€⁰mΣΠTṪ^ḣ√⁰d)De
Try it online!
Finishes all test cases under 1000 in about 11 seconds.
Explanation
Λλ€⁰mΣΠTṪ^ḣ√⁰d)De Implicit inputs, say 12 and 33.
e Put into a list: [12,33]
D Duplicate: [12,33,12,33]
Λ Does this hold for all adjacent pairs:
(12,33 is checked twice but it doesn't matter)
For example, arguments are 33 and 12.
λ ) Anonymous function with arguments 33 (explicit) and 12 (implicit).
d Base-10 digits of implicit argument: [1,2]
ḣ√⁰ Range to square root of explicit argument: [1,2,3,4]
Ṫ^ Outer product with power: [[1,2],[1,4],[1,8],[1,16],[1,32]]
T Transpose: [[1,1,1,1,1],[2,4,8,16,32]]
Π Cartesian product: [[1,2],[1,4],...,[1,32]]
mΣ Map sum: [3,5,...,33]
€⁰ Is the explicit argument in this list? Yes.
Why it works
If we have $B = d_1^{p_1} + cdots + d_n^{p_n}$ where the $d_i$ are digits and $p_i$ are positive integers, then $d_i^{p_i} leq B$ for all $i$, or equivalently $p_i leq log_{d_i} B$.
We can ignore the case $d_i leq 1$, since exponentiating $0$ or $1$ does not change it.
In my program the search space is $1 leq p_i leq sqrt{B}$ (to comply with the time restriction; I would use $1 leq p_i leq B$ otherwise), so if we have $lfloor log_{d_i} B rfloor leq lfloor sqrt{B} rfloor$, then everything is fine.
If $d_i geq 3$, this holds for all natural numbers $B$, so the only dangerous case is $d_i = 2$.
We have $lfloor log_2 B rfloor > lfloor sqrt{B} rfloor$ only for $B = 8$.
In this case $2^3 = 8$, but the search only considers exponents $1$ and $2$.
If the other number number $A$ contains the digit $2$, either it has other nonzero digits as well (so the exponent of $2$ cannot be $3$ in the sum), or $A = 2 cdot 10^k$ for some $k$.
In the latter case, $A$ is not a power of $8$, so it cannot be a copycat of $B$ anyway, and the program correctly returns a falsy value regardless of the other computation.
answered Nov 13 at 20:23
Zgarb
26.3k461228
Great answer which makes me want to learn Husk. Two questions: 1. the implicit argument is mentioned again after you introduce it. When is it used? 2. Could you elaborate on why this algorithm is equivalent to the one posed in the OP?
– Jonah
Nov 15 at 4:28
1
@Jonah 1. The digit functiondtakes the implicit argument. I clarified this in the explanation. 2. I added an argument for the program's correctness.
– Zgarb
Nov 15 at 11:55
Thank you... btw, the part that had confused me was "where does the list of all ones come from?".... rereading i now realize this is merely because all the powers of 1 are just one....
– Jonah
Nov 15 at 18:30
add a comment |
up vote
6
down vote
up vote
6
down vote
Husk, 17 bytes
Λλ€⁰mΣΠTṪ^ḣ√⁰d)De
Try it online!
Finishes all test cases under 1000 in about 11 seconds.
Explanation
Λλ€⁰mΣΠTṪ^ḣ√⁰d)De Implicit inputs, say 12 and 33.
e Put into a list: [12,33]
D Duplicate: [12,33,12,33]
Λ Does this hold for all adjacent pairs:
(12,33 is checked twice but it doesn't matter)
For example, arguments are 33 and 12.
λ ) Anonymous function with arguments 33 (explicit) and 12 (implicit).
d Base-10 digits of implicit argument: [1,2]
ḣ√⁰ Range to square root of explicit argument: [1,2,3,4]
Ṫ^ Outer product with power: [[1,2],[1,4],[1,8],[1,16],[1,32]]
T Transpose: [[1,1,1,1,1],[2,4,8,16,32]]
Π Cartesian product: [[1,2],[1,4],...,[1,32]]
mΣ Map sum: [3,5,...,33]
€⁰ Is the explicit argument in this list? Yes.
Why it works
If we have $B = d_1^{p_1} + cdots + d_n^{p_n}$ where the $d_i$ are digits and $p_i$ are positive integers, then $d_i^{p_i} leq B$ for all $i$, or equivalently $p_i leq log_{d_i} B$.
We can ignore the case $d_i leq 1$, since exponentiating $0$ or $1$ does not change it.
In my program the search space is $1 leq p_i leq sqrt{B}$ (to comply with the time restriction; I would use $1 leq p_i leq B$ otherwise), so if we have $lfloor log_{d_i} B rfloor leq lfloor sqrt{B} rfloor$, then everything is fine.
If $d_i geq 3$, this holds for all natural numbers $B$, so the only dangerous case is $d_i = 2$.
We have $lfloor log_2 B rfloor > lfloor sqrt{B} rfloor$ only for $B = 8$.
In this case $2^3 = 8$, but the search only considers exponents $1$ and $2$.
If the other number number $A$ contains the digit $2$, either it has other nonzero digits as well (so the exponent of $2$ cannot be $3$ in the sum), or $A = 2 cdot 10^k$ for some $k$.
In the latter case, $A$ is not a power of $8$, so it cannot be a copycat of $B$ anyway, and the program correctly returns a falsy value regardless of the other computation.
answered Nov 13 at 20:23
Zgarb
26.3k461228
Husk, 17 bytes
Λλ€⁰mΣΠTṪ^ḣ√⁰d)De
Try it online!
Finishes all test cases under 1000 in about 11 seconds.
Explanation
Λλ€⁰mΣΠTṪ^ḣ√⁰d)De Implicit inputs, say 12 and 33.
e Put into a list: [12,33]
D Duplicate: [12,33,12,33]
Λ Does this hold for all adjacent pairs:
(12,33 is checked twice but it doesn't matter)
For example, arguments are 33 and 12.
λ ) Anonymous function with arguments 33 (explicit) and 12 (implicit).
d Base-10 digits of implicit argument: [1,2]
ḣ√⁰ Range to square root of explicit argument: [1,2,3,4]
Ṫ^ Outer product with power: [[1,2],[1,4],[1,8],[1,16],[1,32]]
T Transpose: [[1,1,1,1,1],[2,4,8,16,32]]
Π Cartesian product: [[1,2],[1,4],...,[1,32]]
mΣ Map sum: [3,5,...,33]
€⁰ Is the explicit argument in this list? Yes.
Why it works
If we have $B = d_1^{p_1} + cdots + d_n^{p_n}$ where the $d_i$ are digits and $p_i$ are positive integers, then $d_i^{p_i} leq B$ for all $i$, or equivalently $p_i leq log_{d_i} B$.
We can ignore the case $d_i leq 1$, since exponentiating $0$ or $1$ does not change it.
In my program the search space is $1 leq p_i leq sqrt{B}$ (to comply with the time restriction; I would use $1 leq p_i leq B$ otherwise), so if we have $lfloor log_{d_i} B rfloor leq lfloor sqrt{B} rfloor$, then everything is fine.
If $d_i geq 3$, this holds for all natural numbers $B$, so the only dangerous case is $d_i = 2$.
We have $lfloor log_2 B rfloor > lfloor sqrt{B} rfloor$ only for $B = 8$.
In this case $2^3 = 8$, but the search only considers exponents $1$ and $2$.
If the other number number $A$ contains the digit $2$, either it has other nonzero digits as well (so the exponent of $2$ cannot be $3$ in the sum), or $A = 2 cdot 10^k$ for some $k$.
In the latter case, $A$ is not a power of $8$, so it cannot be a copycat of $B$ anyway, and the program correctly returns a falsy value regardless of the other computation.
answered Nov 13 at 20:23
Zgarb
26.3k461228
edited Nov 15 at 11:59
answered Nov 13 at 20:23
Zgarb
26.3k461228
answered Nov 13 at 20:23
Zgarb
26.3k461228
answered Nov 13 at 20:23
Zgarb
26.3k461228
26.3k461228
Great answer which makes me want to learn Husk. Two questions: 1. the implicit argument is mentioned again after you introduce it. When is it used? 2. Could you elaborate on why this algorithm is equivalent to the one posed in the OP?
– Jonah
Nov 15 at 4:28
1
@Jonah 1. The digit functiondtakes the implicit argument. I clarified this in the explanation. 2. I added an argument for the program's correctness.
– Zgarb
Nov 15 at 11:55
Thank you... btw, the part that had confused me was "where does the list of all ones come from?".... rereading i now realize this is merely because all the powers of 1 are just one....
– Jonah
Nov 15 at 18:30
add a comment |
Great answer which makes me want to learn Husk. Two questions: 1. the implicit argument is mentioned again after you introduce it. When is it used? 2. Could you elaborate on why this algorithm is equivalent to the one posed in the OP?
– Jonah
Nov 15 at 4:28
1
@Jonah 1. The digit functiondtakes the implicit argument. I clarified this in the explanation. 2. I added an argument for the program's correctness.
– Zgarb
Nov 15 at 11:55
Thank you... btw, the part that had confused me was "where does the list of all ones come from?".... rereading i now realize this is merely because all the powers of 1 are just one....
– Jonah
Nov 15 at 18:30
Great answer which makes me want to learn Husk. Two questions: 1. the implicit argument is mentioned again after you introduce it. When is it used? 2. Could you elaborate on why this algorithm is equivalent to the one posed in the OP?
– Jonah
Nov 15 at 4:28
Great answer which makes me want to learn Husk. Two questions: 1. the implicit argument is mentioned again after you introduce it. When is it used? 2. Could you elaborate on why this algorithm is equivalent to the one posed in the OP?
– Jonah
Nov 15 at 4:28
1
1
@Jonah 1. The digit function
d takes the implicit argument. I clarified this in the explanation. 2. I added an argument for the program's correctness.– Zgarb
Nov 15 at 11:55
@Jonah 1. The digit function
d takes the implicit argument. I clarified this in the explanation. 2. I added an argument for the program's correctness.– Zgarb
Nov 15 at 11:55
Thank you... btw, the part that had confused me was "where does the list of all ones come from?".... rereading i now realize this is merely because all the powers of 1 are just one....
– Jonah
Nov 15 at 18:30
Thank you... btw, the part that had confused me was "where does the list of all ones come from?".... rereading i now realize this is merely because all the powers of 1 are just one....
– Jonah
Nov 15 at 18:30
add a comment |
up vote
4
down vote
Python 2, 102 bytes
lambda a,b:g(a,b)*g(b,a)
g=lambda a,b,e=1:b==a<1or(b>0<=b-e>=0<a)and(g(a/10,b-(a%10)**e)or g(a,b,e+1))
Try it online!
answered Nov 13 at 13:23
ovs
18.3k21059
add a comment |
up vote
4
down vote
Python 2, 102 bytes
lambda a,b:g(a,b)*g(b,a)
g=lambda a,b,e=1:b==a<1or(b>0<=b-e>=0<a)and(g(a/10,b-(a%10)**e)or g(a,b,e+1))
Try it online!
answered Nov 13 at 13:23
ovs
18.3k21059
add a comment |
up vote
4
down vote
up vote
4
down vote
Python 2, 102 bytes
lambda a,b:g(a,b)*g(b,a)
g=lambda a,b,e=1:b==a<1or(b>0<=b-e>=0<a)and(g(a/10,b-(a%10)**e)or g(a,b,e+1))
Try it online!
answered Nov 13 at 13:23
ovs
18.3k21059
Python 2, 102 bytes
lambda a,b:g(a,b)*g(b,a)
g=lambda a,b,e=1:b==a<1or(b>0<=b-e>=0<a)and(g(a/10,b-(a%10)**e)or g(a,b,e+1))
Try it online!
answered Nov 13 at 13:23
ovs
18.3k21059
answered Nov 13 at 13:23
ovs
18.3k21059
answered Nov 13 at 13:23
ovs
18.3k21059
answered Nov 13 at 13:23
ovs
18.3k21059
18.3k21059
add a comment |
add a comment |
up vote
4
down vote
05AB1E, 26 22 bytes
εVтLIàgãεYSym}OIyKå}˜P
Takes the input as a list (i.e. [526,853]).
Try it online or verify most test cases in the range [1,999].
Similar as my old answer below, except that the [1,n] list is hardcoded to [1,100], and it creates the cartesian list twice, once for each input-mapping, which is the main bottleneck in terms of performance.
Old 26 bytes answer that's better for performance:
Z©bgL®gãUεVXεYSym}OsN>èå}P
In this version I traded in some bytes to make the performance a lot better so it can run [1,1000] with ease. Test cases containing numbers in the range [1,9999] are done in about a second on TIO. Test cases in the range [10000,99999] in about 10-15 seconds on TIO. Above that it will timeout.
Try it online or verify all test cases with numbers in the range [1,9999].
Explanation:
Z # Push the max of the (implicit) input-list (without popping)
# i.e. [526,853] → 853
© # Store it in the register (without popping)
b # Convert to binary
# i.e. 853 → 1101010101
g # Take its length
# i.e. 1101010101 → 10
L # Pop and push a list [1, n]
# i.e. 10 → [1,2,3,4,5,6,7,8,9,10]
® # Push the max from the register
g # Take its length
# i.e. 853 → 3
ã # Cartesian product the list that many times
# i.e. [1,2,3,4,5,6,7,8,9,10] and 3
# → [[1,1,1],[1,1,2],[1,1,3],...,[10,10,8],[10,10,9],[10,10,10]]
U # Pop and store it in variable `X`
ε } # Map both values of the input list:
V # Store the current value in variable `Y`
Xε } # Map `y` over the numbers of variable `X`
Y # Push variable `Y`
S # Convert it to a list of digits
# i.e. 526 → [5,2,6]
ym # Take each digit to the power of the current cartesian product sublist
# i.e. [5,2,6] and [3,9,3] → [125,512,216]
O # Take the sum of each inner list
# i.e. [[5,2,6],[5,2,36],[5,2,216],...,[125,512,216],...]
# → [13,43,223,...,853,...]
s # Swap to push the (implicit) input
N> # Push the index + 1
# i.e. 0 → 1
è # Index into the input-list (with automatic wraparound)
# i.e. [526,853] and 1 → 853
å # Check if it's in the list of sums
# i.e. [13,43,223,...,853,...] and 853 → 1
P # Check if it's truthy for both both (and output implicitly)
# i.e. [1,1] → 1
answered Nov 13 at 13:15
Kevin Cruijssen
34.5k554182
add a comment |
up vote
4
down vote
05AB1E, 26 22 bytes
εVтLIàgãεYSym}OIyKå}˜P
Takes the input as a list (i.e. [526,853]).
Try it online or verify most test cases in the range [1,999].
Similar as my old answer below, except that the [1,n] list is hardcoded to [1,100], and it creates the cartesian list twice, once for each input-mapping, which is the main bottleneck in terms of performance.
Old 26 bytes answer that's better for performance:
Z©bgL®gãUεVXεYSym}OsN>èå}P
In this version I traded in some bytes to make the performance a lot better so it can run [1,1000] with ease. Test cases containing numbers in the range [1,9999] are done in about a second on TIO. Test cases in the range [10000,99999] in about 10-15 seconds on TIO. Above that it will timeout.
Try it online or verify all test cases with numbers in the range [1,9999].
Explanation:
Z # Push the max of the (implicit) input-list (without popping)
# i.e. [526,853] → 853
© # Store it in the register (without popping)
b # Convert to binary
# i.e. 853 → 1101010101
g # Take its length
# i.e. 1101010101 → 10
L # Pop and push a list [1, n]
# i.e. 10 → [1,2,3,4,5,6,7,8,9,10]
® # Push the max from the register
g # Take its length
# i.e. 853 → 3
ã # Cartesian product the list that many times
# i.e. [1,2,3,4,5,6,7,8,9,10] and 3
# → [[1,1,1],[1,1,2],[1,1,3],...,[10,10,8],[10,10,9],[10,10,10]]
U # Pop and store it in variable `X`
ε } # Map both values of the input list:
V # Store the current value in variable `Y`
Xε } # Map `y` over the numbers of variable `X`
Y # Push variable `Y`
S # Convert it to a list of digits
# i.e. 526 → [5,2,6]
ym # Take each digit to the power of the current cartesian product sublist
# i.e. [5,2,6] and [3,9,3] → [125,512,216]
O # Take the sum of each inner list
# i.e. [[5,2,6],[5,2,36],[5,2,216],...,[125,512,216],...]
# → [13,43,223,...,853,...]
s # Swap to push the (implicit) input
N> # Push the index + 1
# i.e. 0 → 1
è # Index into the input-list (with automatic wraparound)
# i.e. [526,853] and 1 → 853
å # Check if it's in the list of sums
# i.e. [13,43,223,...,853,...] and 853 → 1
P # Check if it's truthy for both both (and output implicitly)
# i.e. [1,1] → 1
answered Nov 13 at 13:15
Kevin Cruijssen
34.5k554182
add a comment |
up vote
4
down vote
up vote
4
down vote
05AB1E, 26 22 bytes
εVтLIàgãεYSym}OIyKå}˜P
Takes the input as a list (i.e. [526,853]).
Try it online or verify most test cases in the range [1,999].
Similar as my old answer below, except that the [1,n] list is hardcoded to [1,100], and it creates the cartesian list twice, once for each input-mapping, which is the main bottleneck in terms of performance.
Old 26 bytes answer that's better for performance:
Z©bgL®gãUεVXεYSym}OsN>èå}P
In this version I traded in some bytes to make the performance a lot better so it can run [1,1000] with ease. Test cases containing numbers in the range [1,9999] are done in about a second on TIO. Test cases in the range [10000,99999] in about 10-15 seconds on TIO. Above that it will timeout.
Try it online or verify all test cases with numbers in the range [1,9999].
Explanation:
Z # Push the max of the (implicit) input-list (without popping)
# i.e. [526,853] → 853
© # Store it in the register (without popping)
b # Convert to binary
# i.e. 853 → 1101010101
g # Take its length
# i.e. 1101010101 → 10
L # Pop and push a list [1, n]
# i.e. 10 → [1,2,3,4,5,6,7,8,9,10]
® # Push the max from the register
g # Take its length
# i.e. 853 → 3
ã # Cartesian product the list that many times
# i.e. [1,2,3,4,5,6,7,8,9,10] and 3
# → [[1,1,1],[1,1,2],[1,1,3],...,[10,10,8],[10,10,9],[10,10,10]]
U # Pop and store it in variable `X`
ε } # Map both values of the input list:
V # Store the current value in variable `Y`
Xε } # Map `y` over the numbers of variable `X`
Y # Push variable `Y`
S # Convert it to a list of digits
# i.e. 526 → [5,2,6]
ym # Take each digit to the power of the current cartesian product sublist
# i.e. [5,2,6] and [3,9,3] → [125,512,216]
O # Take the sum of each inner list
# i.e. [[5,2,6],[5,2,36],[5,2,216],...,[125,512,216],...]
# → [13,43,223,...,853,...]
s # Swap to push the (implicit) input
N> # Push the index + 1
# i.e. 0 → 1
è # Index into the input-list (with automatic wraparound)
# i.e. [526,853] and 1 → 853
å # Check if it's in the list of sums
# i.e. [13,43,223,...,853,...] and 853 → 1
P # Check if it's truthy for both both (and output implicitly)
# i.e. [1,1] → 1
answered Nov 13 at 13:15
Kevin Cruijssen
34.5k554182
05AB1E, 26 22 bytes
εVтLIàgãεYSym}OIyKå}˜P
Takes the input as a list (i.e. [526,853]).
Try it online or verify most test cases in the range [1,999].
Similar as my old answer below, except that the [1,n] list is hardcoded to [1,100], and it creates the cartesian list twice, once for each input-mapping, which is the main bottleneck in terms of performance.
Old 26 bytes answer that's better for performance:
Z©bgL®gãUεVXεYSym}OsN>èå}P
In this version I traded in some bytes to make the performance a lot better so it can run [1,1000] with ease. Test cases containing numbers in the range [1,9999] are done in about a second on TIO. Test cases in the range [10000,99999] in about 10-15 seconds on TIO. Above that it will timeout.
Try it online or verify all test cases with numbers in the range [1,9999].
Explanation:
Z # Push the max of the (implicit) input-list (without popping)
# i.e. [526,853] → 853
© # Store it in the register (without popping)
b # Convert to binary
# i.e. 853 → 1101010101
g # Take its length
# i.e. 1101010101 → 10
L # Pop and push a list [1, n]
# i.e. 10 → [1,2,3,4,5,6,7,8,9,10]
® # Push the max from the register
g # Take its length
# i.e. 853 → 3
ã # Cartesian product the list that many times
# i.e. [1,2,3,4,5,6,7,8,9,10] and 3
# → [[1,1,1],[1,1,2],[1,1,3],...,[10,10,8],[10,10,9],[10,10,10]]
U # Pop and store it in variable `X`
ε } # Map both values of the input list:
V # Store the current value in variable `Y`
Xε } # Map `y` over the numbers of variable `X`
Y # Push variable `Y`
S # Convert it to a list of digits
# i.e. 526 → [5,2,6]
ym # Take each digit to the power of the current cartesian product sublist
# i.e. [5,2,6] and [3,9,3] → [125,512,216]
O # Take the sum of each inner list
# i.e. [[5,2,6],[5,2,36],[5,2,216],...,[125,512,216],...]
# → [13,43,223,...,853,...]
s # Swap to push the (implicit) input
N> # Push the index + 1
# i.e. 0 → 1
è # Index into the input-list (with automatic wraparound)
# i.e. [526,853] and 1 → 853
å # Check if it's in the list of sums
# i.e. [13,43,223,...,853,...] and 853 → 1
P # Check if it's truthy for both both (and output implicitly)
# i.e. [1,1] → 1
answered Nov 13 at 13:15
Kevin Cruijssen
34.5k554182
edited Nov 13 at 13:28
answered Nov 13 at 13:15
Kevin Cruijssen
34.5k554182
answered Nov 13 at 13:15
Kevin Cruijssen
34.5k554182
answered Nov 13 at 13:15
Kevin Cruijssen
34.5k554182
34.5k554182
add a comment |
add a comment |
up vote
4
down vote
Haskell, 77 bytes
a#b=a!b&&b!a
a!b|a<1=b==0|b<1=b>1|1<2=or[div a 10!(b-mod a 10^e)|e<-[1..b+1]]
Try it online!
answered Nov 13 at 13:39
ovs
18.3k21059
add a comment |
up vote
4
down vote
Haskell, 77 bytes
a#b=a!b&&b!a
a!b|a<1=b==0|b<1=b>1|1<2=or[div a 10!(b-mod a 10^e)|e<-[1..b+1]]
Try it online!
answered Nov 13 at 13:39
ovs
18.3k21059
add a comment |
up vote
4
down vote
up vote
4
down vote
Haskell, 77 bytes
a#b=a!b&&b!a
a!b|a<1=b==0|b<1=b>1|1<2=or[div a 10!(b-mod a 10^e)|e<-[1..b+1]]
Try it online!
answered Nov 13 at 13:39
ovs
18.3k21059
Haskell, 77 bytes
a#b=a!b&&b!a
a!b|a<1=b==0|b<1=b>1|1<2=or[div a 10!(b-mod a 10^e)|e<-[1..b+1]]
Try it online!
answered Nov 13 at 13:39
ovs
18.3k21059
answered Nov 13 at 13:39
ovs
18.3k21059
answered Nov 13 at 13:39
ovs
18.3k21059
answered Nov 13 at 13:39
ovs
18.3k21059
18.3k21059
add a comment |
add a comment |
up vote
4
down vote
Perl 6, 87 84 69 bytes
-15 bytes thanks to nwellnhof!
{!grep {!grep $^b,[X+] 0,|map (*X**1..$b.msb+1),$^a.comb},.[0,1,1,0]}
Try it online!
Anonymous code block that returns True or False.
Explanation:
{!grep {!grep $^b,[X+] 0,|map (*X**1..$b.msb+1),$^a.comb},.[0,1,1,0]}
{ } # Anonymous code block
!grep # None of:
.[0,1,1,0] # The input and the input reverse
{!grep # None of
[X+] # All possible sums of
0,| # 0 (this is to prevent single digit numbers being crossed with themself)
map ,$^a.comb # Each digit mapped to
(*X** ) # The power of
1..$b.msb+1 # All of 1 to the most significant bit of b plus 1
# This could just be b+1, but time constraints...
$^b, # Is equal to b
answered Nov 13 at 11:20
Jo King
19.7k245103
@Arnauld, A Junction is Truthy/Falsey, as I've shown by using the boolify operator before outputting. I golfed it to something else anyway, though I could save a byte if I could output a truthy value for false and vice-versa...?
– Jo King
Nov 13 at 11:40
Thanks for the clarification. About the truthy/falsy inversion: I'd rather say no.
– Arnauld
Nov 13 at 11:45
add a comment |
up vote
4
down vote
Perl 6, 87 84 69 bytes
-15 bytes thanks to nwellnhof!
{!grep {!grep $^b,[X+] 0,|map (*X**1..$b.msb+1),$^a.comb},.[0,1,1,0]}
Try it online!
Anonymous code block that returns True or False.
Explanation:
{!grep {!grep $^b,[X+] 0,|map (*X**1..$b.msb+1),$^a.comb},.[0,1,1,0]}
{ } # Anonymous code block
!grep # None of:
.[0,1,1,0] # The input and the input reverse
{!grep # None of
[X+] # All possible sums of
0,| # 0 (this is to prevent single digit numbers being crossed with themself)
map ,$^a.comb # Each digit mapped to
(*X** ) # The power of
1..$b.msb+1 # All of 1 to the most significant bit of b plus 1
# This could just be b+1, but time constraints...
$^b, # Is equal to b
answered Nov 13 at 11:20
Jo King
19.7k245103
@Arnauld, A Junction is Truthy/Falsey, as I've shown by using the boolify operator before outputting. I golfed it to something else anyway, though I could save a byte if I could output a truthy value for false and vice-versa...?
– Jo King
Nov 13 at 11:40
Thanks for the clarification. About the truthy/falsy inversion: I'd rather say no.
– Arnauld
Nov 13 at 11:45
add a comment |
up vote
4
down vote
up vote
4
down vote
Perl 6, 87 84 69 bytes
-15 bytes thanks to nwellnhof!
{!grep {!grep $^b,[X+] 0,|map (*X**1..$b.msb+1),$^a.comb},.[0,1,1,0]}
Try it online!
Anonymous code block that returns True or False.
Explanation:
{!grep {!grep $^b,[X+] 0,|map (*X**1..$b.msb+1),$^a.comb},.[0,1,1,0]}
{ } # Anonymous code block
!grep # None of:
.[0,1,1,0] # The input and the input reverse
{!grep # None of
[X+] # All possible sums of
0,| # 0 (this is to prevent single digit numbers being crossed with themself)
map ,$^a.comb # Each digit mapped to
(*X** ) # The power of
1..$b.msb+1 # All of 1 to the most significant bit of b plus 1
# This could just be b+1, but time constraints...
$^b, # Is equal to b
answered Nov 13 at 11:20
Jo King
19.7k245103
Perl 6, 87 84 69 bytes
-15 bytes thanks to nwellnhof!
{!grep {!grep $^b,[X+] 0,|map (*X**1..$b.msb+1),$^a.comb},.[0,1,1,0]}
Try it online!
Anonymous code block that returns True or False.
Explanation:
{!grep {!grep $^b,[X+] 0,|map (*X**1..$b.msb+1),$^a.comb},.[0,1,1,0]}
{ } # Anonymous code block
!grep # None of:
.[0,1,1,0] # The input and the input reverse
{!grep # None of
[X+] # All possible sums of
0,| # 0 (this is to prevent single digit numbers being crossed with themself)
map ,$^a.comb # Each digit mapped to
(*X** ) # The power of
1..$b.msb+1 # All of 1 to the most significant bit of b plus 1
# This could just be b+1, but time constraints...
$^b, # Is equal to b
answered Nov 13 at 11:20
Jo King
19.7k245103
edited Nov 14 at 10:03
answered Nov 13 at 11:20
Jo King
19.7k245103
answered Nov 13 at 11:20
Jo King
19.7k245103
answered Nov 13 at 11:20
Jo King
19.7k245103
19.7k245103
@Arnauld, A Junction is Truthy/Falsey, as I've shown by using the boolify operator before outputting. I golfed it to something else anyway, though I could save a byte if I could output a truthy value for false and vice-versa...?
– Jo King
Nov 13 at 11:40
Thanks for the clarification. About the truthy/falsy inversion: I'd rather say no.
– Arnauld
Nov 13 at 11:45
add a comment |
@Arnauld, A Junction is Truthy/Falsey, as I've shown by using the boolify operator before outputting. I golfed it to something else anyway, though I could save a byte if I could output a truthy value for false and vice-versa...?
– Jo King
Nov 13 at 11:40
Thanks for the clarification. About the truthy/falsy inversion: I'd rather say no.
– Arnauld
Nov 13 at 11:45
@Arnauld, A Junction is Truthy/Falsey, as I've shown by using the boolify operator before outputting. I golfed it to something else anyway, though I could save a byte if I could output a truthy value for false and vice-versa...?
– Jo King
Nov 13 at 11:40
@Arnauld, A Junction is Truthy/Falsey, as I've shown by using the boolify operator before outputting. I golfed it to something else anyway, though I could save a byte if I could output a truthy value for false and vice-versa...?
– Jo King
Nov 13 at 11:40
Thanks for the clarification. About the truthy/falsy inversion: I'd rather say no.
– Arnauld
Nov 13 at 11:45
Thanks for the clarification. About the truthy/falsy inversion: I'd rather say no.
– Arnauld
Nov 13 at 11:45
add a comment |
up vote
4
down vote
JavaScript (Node.js), 116 92 89 86 83 77 bytes
a=>b=>(G=(c,g,f=h=g%10)=>g?c>f&f>1&&G(c,g,h*f)||G(c-f,g/10|0):!c)(a,b)&G(b,a)
Try it online!
Expect input as (A)(B).
answered Nov 13 at 11:34
Shieru Asakoto
2,370314
Strings are fine. (I've clarified the input format in the challenge.)
– Arnauld
Nov 13 at 11:41
@Arnauld Oh I've just found a method not using string but also 108 bytes.
– Shieru Asakoto
Nov 13 at 11:48
add a comment |
up vote
4
down vote
JavaScript (Node.js), 116 92 89 86 83 77 bytes
a=>b=>(G=(c,g,f=h=g%10)=>g?c>f&f>1&&G(c,g,h*f)||G(c-f,g/10|0):!c)(a,b)&G(b,a)
Try it online!
Expect input as (A)(B).
answered Nov 13 at 11:34
Shieru Asakoto
2,370314
Strings are fine. (I've clarified the input format in the challenge.)
– Arnauld
Nov 13 at 11:41
@Arnauld Oh I've just found a method not using string but also 108 bytes.
– Shieru Asakoto
Nov 13 at 11:48
add a comment |
up vote
4
down vote
up vote
4
down vote
JavaScript (Node.js), 116 92 89 86 83 77 bytes
a=>b=>(G=(c,g,f=h=g%10)=>g?c>f&f>1&&G(c,g,h*f)||G(c-f,g/10|0):!c)(a,b)&G(b,a)
Try it online!
Expect input as (A)(B).
answered Nov 13 at 11:34
Shieru Asakoto
2,370314
JavaScript (Node.js), 116 92 89 86 83 77 bytes
a=>b=>(G=(c,g,f=h=g%10)=>g?c>f&f>1&&G(c,g,h*f)||G(c-f,g/10|0):!c)(a,b)&G(b,a)
Try it online!
Expect input as (A)(B).
answered Nov 13 at 11:34
Shieru Asakoto
2,370314
edited Nov 15 at 5:51
answered Nov 13 at 11:34
Shieru Asakoto
2,370314
answered Nov 13 at 11:34
Shieru Asakoto
2,370314
answered Nov 13 at 11:34
Shieru Asakoto
2,370314
2,370314
Strings are fine. (I've clarified the input format in the challenge.)
– Arnauld
Nov 13 at 11:41
@Arnauld Oh I've just found a method not using string but also 108 bytes.
– Shieru Asakoto
Nov 13 at 11:48
add a comment |
Strings are fine. (I've clarified the input format in the challenge.)
– Arnauld
Nov 13 at 11:41
@Arnauld Oh I've just found a method not using string but also 108 bytes.
– Shieru Asakoto
Nov 13 at 11:48
Strings are fine. (I've clarified the input format in the challenge.)
– Arnauld
Nov 13 at 11:41
Strings are fine. (I've clarified the input format in the challenge.)
– Arnauld
Nov 13 at 11:41
@Arnauld Oh I've just found a method not using string but also 108 bytes.
– Shieru Asakoto
Nov 13 at 11:48
@Arnauld Oh I've just found a method not using string but also 108 bytes.
– Shieru Asakoto
Nov 13 at 11:48
add a comment |
up vote
2
down vote
J, 56 bytes
h~*h=.4 :'x e.+/|:>,{x 4 :''<y&*^:(x&>)^:a:y''"+"."+":y'
Try it online!
Yay, nested explicit definition!
How it works
powers =. 4 :'<y&*^:(x&>)^:a:y' Explicit aux verb. x = target, y = digit
y Starting from y,
y&*^: ^:a: collect all results of multiplying y
(x&>) until the result is at least x
< Box it.
h=.4 :'x e.+/|:>,{x powers"+"."+":y' Explicit aux verb. x, y = two input numbers
"."+":y Digits of y
x powers"+ Collect powers of digits of y under x
{ Cartesian product of each item
+/|:>, Format correctly and compute the sums
x e. Does x appear in the list of sums?
h~*h Tacit main verb. x, y = two input numbers
Since h tests the condition in only one direction,
test again the other way around (~) and take the AND.
answered Nov 16 at 0:31
Bubbler
6,044759
add a comment |
up vote
2
down vote
J, 56 bytes
h~*h=.4 :'x e.+/|:>,{x 4 :''<y&*^:(x&>)^:a:y''"+"."+":y'
Try it online!
Yay, nested explicit definition!
How it works
powers =. 4 :'<y&*^:(x&>)^:a:y' Explicit aux verb. x = target, y = digit
y Starting from y,
y&*^: ^:a: collect all results of multiplying y
(x&>) until the result is at least x
< Box it.
h=.4 :'x e.+/|:>,{x powers"+"."+":y' Explicit aux verb. x, y = two input numbers
"."+":y Digits of y
x powers"+ Collect powers of digits of y under x
{ Cartesian product of each item
+/|:>, Format correctly and compute the sums
x e. Does x appear in the list of sums?
h~*h Tacit main verb. x, y = two input numbers
Since h tests the condition in only one direction,
test again the other way around (~) and take the AND.
answered Nov 16 at 0:31
Bubbler
6,044759
add a comment |
up vote
2
down vote
up vote
2
down vote
J, 56 bytes
h~*h=.4 :'x e.+/|:>,{x 4 :''<y&*^:(x&>)^:a:y''"+"."+":y'
Try it online!
Yay, nested explicit definition!
How it works
powers =. 4 :'<y&*^:(x&>)^:a:y' Explicit aux verb. x = target, y = digit
y Starting from y,
y&*^: ^:a: collect all results of multiplying y
(x&>) until the result is at least x
< Box it.
h=.4 :'x e.+/|:>,{x powers"+"."+":y' Explicit aux verb. x, y = two input numbers
"."+":y Digits of y
x powers"+ Collect powers of digits of y under x
{ Cartesian product of each item
+/|:>, Format correctly and compute the sums
x e. Does x appear in the list of sums?
h~*h Tacit main verb. x, y = two input numbers
Since h tests the condition in only one direction,
test again the other way around (~) and take the AND.
answered Nov 16 at 0:31
Bubbler
6,044759
J, 56 bytes
h~*h=.4 :'x e.+/|:>,{x 4 :''<y&*^:(x&>)^:a:y''"+"."+":y'
Try it online!
Yay, nested explicit definition!
How it works
powers =. 4 :'<y&*^:(x&>)^:a:y' Explicit aux verb. x = target, y = digit
y Starting from y,
y&*^: ^:a: collect all results of multiplying y
(x&>) until the result is at least x
< Box it.
h=.4 :'x e.+/|:>,{x powers"+"."+":y' Explicit aux verb. x, y = two input numbers
"."+":y Digits of y
x powers"+ Collect powers of digits of y under x
{ Cartesian product of each item
+/|:>, Format correctly and compute the sums
x e. Does x appear in the list of sums?
h~*h Tacit main verb. x, y = two input numbers
Since h tests the condition in only one direction,
test again the other way around (~) and take the AND.
answered Nov 16 at 0:31
Bubbler
6,044759
answered Nov 16 at 0:31
Bubbler
6,044759
answered Nov 16 at 0:31
Bubbler
6,044759
answered Nov 16 at 0:31
Bubbler
6,044759
6,044759
add a comment |
add a comment |
up vote
1
down vote
Python 2, 149 147 143 139 132 118 108 107 106 105 bytes
lambda a,b:g(a,b)*g(b,a)
g=lambda a,b:any(g(a/10,b-(a%10)**-~i)for i in(a*b>0)*range(len(bin(b))))or b==0
Try it online!
-4 bytes, thanks to Vedant Kandoi
answered Nov 13 at 11:32
TFeld
13.7k21239
>0can be removed.not a:a<1.b==0:b<1
– Vedant Kandoi
Nov 13 at 11:37
@VedantKandoi Thanks, thoughb<0doesn't work
– TFeld
Nov 13 at 11:41
add a comment |
up vote
1
down vote
Python 2, 149 147 143 139 132 118 108 107 106 105 bytes
lambda a,b:g(a,b)*g(b,a)
g=lambda a,b:any(g(a/10,b-(a%10)**-~i)for i in(a*b>0)*range(len(bin(b))))or b==0
Try it online!
-4 bytes, thanks to Vedant Kandoi
answered Nov 13 at 11:32
TFeld
13.7k21239
>0can be removed.not a:a<1.b==0:b<1
– Vedant Kandoi
Nov 13 at 11:37
@VedantKandoi Thanks, thoughb<0doesn't work
– TFeld
Nov 13 at 11:41
add a comment |
up vote
1
down vote
up vote
1
down vote
Python 2, 149 147 143 139 132 118 108 107 106 105 bytes
lambda a,b:g(a,b)*g(b,a)
g=lambda a,b:any(g(a/10,b-(a%10)**-~i)for i in(a*b>0)*range(len(bin(b))))or b==0
Try it online!
-4 bytes, thanks to Vedant Kandoi
answered Nov 13 at 11:32
TFeld
13.7k21239
Python 2, 149 147 143 139 132 118 108 107 106 105 bytes
lambda a,b:g(a,b)*g(b,a)
g=lambda a,b:any(g(a/10,b-(a%10)**-~i)for i in(a*b>0)*range(len(bin(b))))or b==0
Try it online!
-4 bytes, thanks to Vedant Kandoi
answered Nov 13 at 11:32
TFeld
13.7k21239
edited Nov 13 at 12:25
answered Nov 13 at 11:32
TFeld
13.7k21239
answered Nov 13 at 11:32
TFeld
13.7k21239
answered Nov 13 at 11:32
TFeld
13.7k21239
13.7k21239
>0can be removed.not a:a<1.b==0:b<1
– Vedant Kandoi
Nov 13 at 11:37
@VedantKandoi Thanks, thoughb<0doesn't work
– TFeld
Nov 13 at 11:41
add a comment |
>0can be removed.not a:a<1.b==0:b<1
– Vedant Kandoi
Nov 13 at 11:37
@VedantKandoi Thanks, thoughb<0doesn't work
– TFeld
Nov 13 at 11:41
>0 can be removed. not a:a<1. b==0:b<1– Vedant Kandoi
Nov 13 at 11:37
>0 can be removed. not a:a<1. b==0:b<1– Vedant Kandoi
Nov 13 at 11:37
@VedantKandoi Thanks, though
b<0 doesn't work– TFeld
Nov 13 at 11:41
@VedantKandoi Thanks, though
b<0 doesn't work– TFeld
Nov 13 at 11:41
add a comment |
up vote
1
down vote
J, 68 bytes
I thought J would perform quite well here, but it ended up being tougher than I expected and would love any suggestions for further golfing...
g=.#@#:@[
1 1-:[:(([:+./[=1#.]^"#.1+g#.inv[:i.g^#@])"."0@":)/"1],:|.
Try it online!
NOTE: we subtract 3 chars from the TIO count there since f=. on the main function doesn't count
ungolfed
1 1 -: [: (([: +./ [ = 1 #. ] ^"#. 1 + g #.inv [: i. g ^ #@]) "."0@":)/"1 ] ,: |.
answered Nov 15 at 3:49
Jonah
1,981816
add a comment |
up vote
1
down vote
J, 68 bytes
I thought J would perform quite well here, but it ended up being tougher than I expected and would love any suggestions for further golfing...
g=.#@#:@[
1 1-:[:(([:+./[=1#.]^"#.1+g#.inv[:i.g^#@])"."0@":)/"1],:|.
Try it online!
NOTE: we subtract 3 chars from the TIO count there since f=. on the main function doesn't count
ungolfed
1 1 -: [: (([: +./ [ = 1 #. ] ^"#. 1 + g #.inv [: i. g ^ #@]) "."0@":)/"1 ] ,: |.
answered Nov 15 at 3:49
Jonah
1,981816
add a comment |
up vote
1
down vote
up vote
1
down vote
J, 68 bytes
I thought J would perform quite well here, but it ended up being tougher than I expected and would love any suggestions for further golfing...
g=.#@#:@[
1 1-:[:(([:+./[=1#.]^"#.1+g#.inv[:i.g^#@])"."0@":)/"1],:|.
Try it online!
NOTE: we subtract 3 chars from the TIO count there since f=. on the main function doesn't count
ungolfed
1 1 -: [: (([: +./ [ = 1 #. ] ^"#. 1 + g #.inv [: i. g ^ #@]) "."0@":)/"1 ] ,: |.
answered Nov 15 at 3:49
Jonah
1,981816
J, 68 bytes
I thought J would perform quite well here, but it ended up being tougher than I expected and would love any suggestions for further golfing...
g=.#@#:@[
1 1-:[:(([:+./[=1#.]^"#.1+g#.inv[:i.g^#@])"."0@":)/"1],:|.
Try it online!
NOTE: we subtract 3 chars from the TIO count there since f=. on the main function doesn't count
ungolfed
1 1 -: [: (([: +./ [ = 1 #. ] ^"#. 1 + g #.inv [: i. g ^ #@]) "."0@":)/"1 ] ,: |.
answered Nov 15 at 3:49
Jonah
1,981816
answered Nov 15 at 3:49
Jonah
1,981816
answered Nov 15 at 3:49
Jonah
1,981816
answered Nov 15 at 3:49
Jonah
1,981816
1,981816
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f175841%2freciprocal-copycats%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Suggested case:
17 2401 -> false. I'm almost tripped on this.– Shieru Asakoto
Nov 15 at 5:46