10
\$\begingroup\$

Objective

Given a nonnegative fraction whose denominator is a power of 2, decide whether its (finite-length) binary expansion is symmetric by the radix point.

I/O format

It is assumed that the input is a reduced fraction. Inputs that don't fit into this format fall in don't care situation. Otherwise flexible.

Examples

Truthy

Input = Binary expansion 0/1 = 0.0 3/2 = 1.1 9/4 = 10.01 15/4 = 11.11 

Falsy

1/1 = 1.0 2/1 = 10.0 1/2 = 0.1 5/2 = 10.1 1/4 = 0.01 

Don't care (Invalid inputs)

1/3 2/3 1/5 1/6 -1 
\$\endgroup\$
3
  • \$\begingroup\$ Is 0/2 a valid input? \$\endgroup\$ Commented Oct 8, 2024 at 21:51
  • 3
    \$\begingroup\$ @Arnauld: I wouldn't think so—that could be reduced to 0/1. \$\endgroup\$ Commented Oct 8, 2024 at 21:56
  • 4
    \$\begingroup\$ Suggested testcase 57/8 (falsy). As currently, simply testing if numerator can be divided by 3 passes all testcases. \$\endgroup\$ Commented Oct 9, 2024 at 6:13

11 Answers 11

5
\$\begingroup\$

Python 2, 43 bytes

lambda a,b:int(bin(a/b*2+1)[:1:-1],2)^a%b^b 

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Nekomata + -e, 7 bytes

Ƃ;↔=#Ë= 

Attempt This Online!

Takes input as numerator denominator.

Ƃ;↔=#Ë= Ƃ Convert the numerator to binary digits ; Split the digits into two parts ↔ Reverse the second part = Check if equal to the first part # Take its length Ë Power of 2 = Check if equal to the denominator 
\$\endgroup\$
4
\$\begingroup\$

Python 3, 55 bytes

lambda a,b:bin(a//b)[:1:-1]==f'{a%b:0{len(bin(b))-3}b}' 

Takes input like f(numerator, denominator).

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 19 bytes

≔↨N²θ∧⁼θ⮌θ⁼Lθ⊗⊖L↨N² 

Try it online! Link is to verbose version of code. Takes two integers as input. Explanation:

≔↨N²θ 

Convert the first integer to base 2.

∧⁼θ⮌θ⁼Lθ⊗⊖L↨N² 

Check that it equals its reverse and that its length is twice one less than the length of the base 2 of the second integer.

At some point, I may get around to fixing BaseString on ATO so that it actually works with decimal values (it can convert back from a string that includes a fractional part but the code to convert to string is broken). At that point, for 17 bytes:

≔⍘N²θ∨⁼0θ∧№θ.⁼θ⮌θ 

Attempt This Online! Link is to verbose version of code. Takes the fraction in decimal as input. Explanation:

≔⍘N²θ 

Input the value and convert it to binary.

∨⁼0θ∧№θ.⁼θ⮌θ 

Check that it's either the literal 0 or it contains a . and equals its reverse.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 32 bytes

q=>g=p=>(q>>=1)?g(p/2^p%2*q*q):p 

Try it online!

Instead of accept reduced form p/q, this function may accept any even number q as well. We can extends the definition about symmetry as padding 0s at beginning do not affect the number value.

First, if q == 1, the output should be true iff p == 0.

Otherwise, we recursively test if bits read from right is matching bits read from left: We simply check if the last bit (p%2) is matching to the first bit (p&q*q/2). If they are matching, clear them to 0 and divide p by 2. So we can test remaining bits. If they do not match, set the left side bit to 1 on p and also divide p by 2. And after iteration, p must left to be non-zero. q is shifted right by 1 in each iteration. And the iteration is done as long as q == 1.

\$\endgroup\$
3
\$\begingroup\$

x86-64 machine code, 17 bytes

31 D2 A9 D1 EF 11 D2 D1 EE 75 F8 39 FA 0F 94 C0 C3 

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes the numerator in EDI and the denominator in ESI as 32-bit integers, and returns a Boolean value in AL, 1 if symmetric and 0 if not.

In assembly:

f: xor edx, edx # Set EDX to 0. .byte 0xA9 # Subsumes the following two instructions into 'test eax, 0xD211EFD1'. r: shr edi, 1 # Shift EDI right by 1 bit. The removed bit goes into CF. adc edx, edx # Add EDX+CF to EDX, which puts the bit from CF onto that value. shr esi, 1 # Shift ESI right by 1 bit. jnz r # Jump back, to repeat, if the result is nonzero. # If the denominator is 2^n, n bit transfers will take place. cmp edx, edi # Compare the values of EDX and EDI. sete al # Set AL to 1 if they are equal, 0 otherwise. ret # Return. 
\$\endgroup\$
3
\$\begingroup\$

Java, 49 bytes

(d,n)->{while((d/=2)>0)n=n/2^n%2*d*d;return n<1;} 

Iterative port of @tsh's first JavaScript answer.

Try it online.

Explanation:

(d,n)->{ // Method with two integer parameters and boolean return-type while((d/=2) // Before every iteration, integer-divide `d` by 2 >0) // Continue looping as long as it isn't 0 yet: n= // Change `n` to: n/2 // `n` integer-divided by 2 ^ // bitwised-XOR'ed by: n%2 // `n` modulo-2 *d*d; // multiplied by the square of `d` return n<1;} // After the loop: return whether `n` is now 0 
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Could you please swap the variable names n and d? Currently n is the denominator and d is the numerator. \$\endgroup\$ Commented Oct 20, 2024 at 20:15
3
\$\begingroup\$

Regex (ECMAScript), 112 104 bytes

^(x+),((?=\1*.*?(((x+)(?=\5$))*)x$)(?=.*(?=\1$)(x(x(x*)\8))(?=\6*$)\3\7*$)(?=.*(?=\1*$)(\1\8+$))\9x\3)*$

Takes denominator and numerator (in that order) from input in unary as strings of xs whose length represents the number, separated by a ,.

Try it online! - test cases only
Try it online! - all reducible numerators / denominators up to 256

ECMAScript regex is incapable of matching unbounded palindromes, but it can match binary palindromes that are encoded in unary.

In this regex flavor it is not possible to keep track of more than one changing number in a loop (and that one number can only decrease), so this regex's main loop works by preserving the property of symmetry at each step, if that property exists in the input.

This works by starting from the middle and going outward. On each step, it finds the largest \$1\$ bit in the right half (i.e. less than the denominator) and subtracts it from \$tail\$, along with the power of \$2\$ corresponding to the mirrored bit in the left half. (It doesn't need to actually check if that left-side bit is \$1\$, because if it isn't, the calculation of that bit's value will either fail due to not fitting in \$tail\$, or \$1\$ will be subtracted from a \$0\$ bit, resulting in borrow, but making it impossible to end with \$tail=0\$.) Then iff at the end \$tail=0\$, the input fraction was symmetric.

It does not work by going from the outside in, finding the largest remaining \$1\$ bit in the left half and subtracting it from both halves, because although this would slightly streamline the matching of each left-side bit, the full regex would be much longer. The mirroring of each bit would take two divisions (instead of one division and one multiplication), and detection of each right-side bit being \$1\$ would need to be done explicitly (with modulo and comparison).

It uses the first shortened form of division, which is possible thanks to the divisor always being a prime power. (Grimmy's further shortening trick isn't applicable because capturing \$divisor-1\$ costs nothing in this case.)

^ # tail = denominator (x+) # \1 = tail (assumed to be a power of 2 ≥ 2) , # tail = numerator ( # Begin main loop (?= \1* # tail = tail % \1 .*? (((x+)(?=\5$))*) # \3 = {largest power of 2 ≤ tail} - 1 x$ ) (?= .*(?=\1$) # tail = \1 # Do the division: \6 = tail / (\3 + 1), assuming dividend > 0 (x(x(x*)\8)) # \6 = conjectured quotient - find the largest one that # matches the following assertions; \7 = \6-1; # \8 = (\7 - 1) / 2 = \6 / 2 - 1; tail -= \6 (?=\6*$) # Assert tail is divisible by quotient # The test for divisibility by \3 can be omitted because # the divisor is a prime power. \3\7*$ # Assert tail-(divisor-1) is divisible by quotient-1 ) (?= .*(?=\1*$) # tail = \1 * (\8 + 1), where \1 > \8+1 (\1\8+$) # \9 = tail, the result of the multiplication ) \9 # tail -= \9 x\3 # tail -= \3 + 1 )* # Iterate the above as many times as possible, which can # be as low as zero. $ # Assert tail == 0 
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 45 bytes

Expects (numerator)(denominator). Returns 0 for truthy, or 1 for falsy.

p=>q=>(g=k=>k&&(k^p/(q/=2))&1|g(k/2))(p,q*=q) 

Try it online!

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 11 bytes

b0ÛDÂQ*g;oQ 

Inputs in the order \$n,d\$.

Attempt it online or verify all test cases.

Explanation:

b # Convert the first (implicit) input-numerator to a binary-string 0Û # Trim leading 0s, to fix edge case n=0 to "" D # Duplicate this binary string ÂQ # Check if it's a palindrome  # Bifurcate; short for Duplicate & Reverse copy Q # Check if the two are equal * # Multiply it to the binary string ("" remains "") g # Pop and push its length ; # Halve it o # Get 2 to the power this halved length Q # Check whether it is equal to the second (implicit) input-denominator # (after which the result is output implicitly) 
\$\endgroup\$
2
\$\begingroup\$

APL+WIN, 34 bytes

Prompts for numerator followed by denominator:

i=+/(⌽i↓n)=(i←d÷2)↑n←((d←2⌈⎕)⍴2)⊤⎕ 

Try it online! Thanks to Dyalog Classic

\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.