Halting problem in number theory

[José Manuel Rodríguez Caballero]

Annatala wrote:

> Take the symmetric difference between the set of divisors of n and this
> set where each element is multiplied by 2. Write the result in increasing
> order. For any odd number in the list, type an opening parenthesis, for any
> even number, type a closing parenthesis. The fact that this word is
> well-matched was proved in [2].
>
> For example, take n = 12. The divisors of 12 are 1, 2, 4, 6, 12. Twice
> these divisors: 2, 4, 8, 12, 24. The symmetric difference is 1, 6, 8, 12.
> Hence, the parentheses are ( ( ) ).
>

I agree, I forgot to include 3 among the divisors of 12 (I was writing too
fast, sorry about that). So, let's correct the arithmetic in this example:


divisors of 12: 1, 2, 3, 4, 6, 12
divisors of 12 multiplied by 2: 2, 4, 6, 8, 12, 24
symmetric difference: 1, 3, 8, 24
reduction mod 2: 1, 1, 0, 0
parentheses: ( ( ) )
and this is the result in the code:

def parentheses(n):
    P = set(divisors(n))
    R = sorted(P.symmetric_difference({2*d for d in P}))
    return ''.join('(' if x%2==1 else ')' for x in R)

The problem is, given a parenthesis s, is there a number n such that
parentheses(n)
= s? I think that it is undecidable.

Kind regards,
Jose M.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20211207/08a335d3/attachment.html>