Questions about quadratic residues

Let P denote the set of all primes and, for p \in P, let (*/p) denote the Legendre quadratic residue symbol mod p. Let {\mathbb N}=\{1,2,\dots\} denote the set of natural numbers and let

L: {\mathbb N}\to \{-1,0,1\}^P,

denote the mapping L(n)=( (n/2), (n/3), (n/5), \dots), so the kth component of L(n) is L(n)_k=(n/p_k) where p_k denotes the kth prime in P. The following result is “well-known” (or, as the joke goes, it’s well-known to those who know it well:-).

Theorem: The restriction of L to the subset {\mathbb S} of square-free integers is an injection.

In fact, one can be a little more precise. Let P_{\leq M} denote the set of the first M primes, let {\mathbb S}_N denote the set of square-free integers \leq N, and let

L_M: {\mathbb N}\to \{-1,0,1\}^{P_M},

denote the mapping L_M(n)=( (n/2), (n/3), (n/5), \dots, (n/p_M)).

Theorem: For each N>1, there is an M=M(N)>1 such that the restriction of L_M to the subset {\mathbb S}_N is an injection.

I am no expert in this field, so perhaps the following question is known.

Question: Can one give an effective upper bound on M=M(N)>1 as a function of N>1?

I’ve done some computer computations using SageMath and it seems to me that

M=O(N)

(i.e., there is a linear bound) is possible. On the other hand, my computations were pretty limited, so that’s just a guess.

Michael Reid’s Happy New Year Puzzle, 2012

Here is another puzzle from Michael Reid on NOBNET. (Michael also notes that if you find a solution (a,b,c,d,e,f) then (d,e,f,a,b,c) is another solution.)

Puzzle: Replace a, b, c, d, e, f with the first six prime numbers, in some order, to make the expression a\cdot b^c + d \cdot e^f equal to the New Year.

Best wishes for a happy, healthy and prosperous New Year!

Michael Reid’s Digit operation puzzles

Michael Reid (http://www.math.ucf.edu/~reid/index.html) posted these questions on Nobnet recently. I’m reposting them here.

Consider two rules for modifying a positive integer:

i) replace a substring of its digits by the square of the number represented by the substring
ii) if a substring is a perfect cube, replace the substring by its cube root

Neither the substring being replaced, nor the string replacing it may have leading zeroes.

For example, starting with 123, we may square `23′ to obtain 1529. Then we can square `29′ to get 15841, then square `5′ to get 125841, and then we could take the cube root of `125′ to get 5841, and so on.

What is the smallest number we can obtain from the number 2011 with a sequence of these operations?

Now suppose the two operations are instead

iii) replace a substring by its cube
iv) replace a substring which is a square by its square root

What is the smallest number we can get with these operations if we start from 2011?

Here is another “digit operations” puzzle that I hope you will find a nice challenge.

Consider two rules for modifying a positive integer:

i) replace a substring of its digits by 7 times the number represented by the substring
ii) if a substring is a perfect 7th power, replace the substring by its 7th root

Neither the substring being replaced, nor the string replacing it may have leading zeroes.

For example, starting with 347, we may replace the substring `34′ by `238′ (multiplying by 7) to obtain 2387. Then we can multiply the substring `3′ to get 22187. Now we can take the 7th root of `2187′ to get 23, and so on.

What is the smallest number we can obtain from the number 2011 with a sequence of these operations?

Now suppose the two operations are instead

iii) if a substring is divisible by 7, we may divide the substring by 7
iv) replace a substring by its 7th power

(which are the reverses of operations i) and ii) above).

What is the smallest number we can get with these operations if we start from 2011?