Non-trivial "I know what number you're thinking of"

Consider the following 'trick' (WARNING: very lame)

Think of a number. Multiply this number by two. Add four. Divide the number by two. Subtract the number you were originally thinking of. I guess that the number now in your head is two.

This trick might stump non-mathematicians for a few minutes, but most people will eventually figure it out. The trick relies on the distributive law of numbers, which is not entirely trivial, but most people will find the trick rather lame once they figure it out.

I was wondering if it is possible to do a "I know what number you're thinking of" that relies on less trivial results, from number theory for example, tricks that require some heavier results to explain and are thus more 'magical'. Too avoid being flagged as too subjective or vague, I will try to specify this.

Consider two people, the mathematician $M$ and the non-mathematician $N$. $M$ asks $N$ to think of a number ($M$ may restrict the numbers from which to choose to a sufficiently large set, like the numbers between 1 and 1000 or the prime numbers) and then lets $N$ apply a finite sequence of functions to this number. These functions should preferably be easy and well-known, i.e. basic arithmetic operations, division with residue, decimal representation of a number (e.g. "take the fifth digit"), à la limite prime factorisation, but no functions which require a calculator like trigonometric functions. The following two conditions are imposed:

The function must have a finite image, i.e., $M$ should be able to give a finite, preferably small, set in which the image of the function always lies. For example "Either you're thinking of 5 or you're thinking of 29" would still impress $N$. On the other hand, the trick bellow relies on some serious number theory, but gives an infinite image, which I think is less impressing to most people.

Think of a natural number which cannot be written as a sum of three squares of natural numbers. If the number you're thinking of is divisible by four, divide it by four. Keep dividing by four untill you can no longer do so in $\mathbb{N}$. Add one to the number you now have. The number you end up with is divisible by eight.

The function uses specific properties of the natural numbers or integers, not just algebraic manipulations. This is what I mean by non-trivial. In particular, the same trick should not work in any commutative ring $A$. For example, tricks relying on the fact that $\mathbb{Z}/p\mathbb{Z}$ is a field for any $p$ prime could satisfy this.

I'd be interested in knowing what's possible here.

Solution 1:

I have a "magic trick" I like to perform for classes on a random day throughout the semester (I cannot take credit for its creation! I do not know the original source...).

"Magic" trick:

Pick a four digit number with at least two distinct digits (four is completely arbitrary).
Rearrange this number any way you like, swapping at least one pair of digits (it can be any non-identity permutation).
Subtract the smaller of these two numbers from the larger, the original and mixed-up. For example, if you pick $3572$ as your number and mix it up to form $7235$, you'll subtract $7325 - 3572 = 3753$. (It actually doesn't need to be $\text{larger} - \text{smaller}$, but negatives confuse the class, even though they don't matter mathematically)
Now take the result of the subtraction, and keep one of its nonzero digits a secret. Tell me the other digits in any order you like. (I tell the class that picking $0$ is "too boring!" After reading and seeing how this trick works, think about why I won't let them pick $0$.)

I will know your secret digit by the time you've told me your last digit. How can I possibly do that?

"Magic" Revealed:

Recall that the sum of digits of a number $n$ (the "digital root") is the remainder upon division of $n$ by $9$. But clearly any permutation of the digits doesn't affect this sum, so our original number $n$ and our mixed up number $n'$ have the same digital root, so that $n - n' \equiv 0 \pmod 9$. Thus, having told our participant to keep any nonzero digit to themselves, their secret digit must be whatever it takes to make the sum of digits $0 \bmod 9$. For example, suppose I'm given the digits $3, 3,$ and $7$ (perhaps the participant chose $7325 - 3572$ as their difference). Their sum is $3 + 3 + 7 \equiv 4 \pmod 9$, and they must have been keeping $5$ to themselves, since $4 + 5 \equiv 0 \pmod 9$.

It's certainly not the deepest mathematics involved, but I consider it nontrivial -- and quite fun!

Solution 2:

Kaprekar's constant

Start with any number of up to $4$ digits, with at least two different digits: add leading $0$'s if necessary to make $4$ digits. Write the digits in decreasing order and in increasing order, and subtract the second from the first. Repeat $7$ times. The result will be $6174$.

For example: start with $1234$

$4321 - 1234 = 3087$

$8730 - 0378 = 8352$

$8532 - 2358 = 6174$

$7641 - 1467 = 6174$ (4 times)

EDIT: You might also look at some of the answers to this MathOverflow question.

Solution 3:

Maybe a little off topic but I got given something similar a few years ago:

Pick a number from [1, 10]
Multiply the number by 9
If the result is 2 digits sum them, otherwise continue with your number
Subtract 5
Map your answer to a letter of the alphabet (1=A, 2=B etc )
Think of a country who's name begins with the letter
Take the second letter of the country's name and think of an animal that begins with that letter
Think of the colour of that animal

Grey elephants don't live in Denmark!

Solution 4:

Pick any integer number between 100 and 999. Write it again next to the number, and now you have a 6 digits number. Divide it by 7, divide it by 11, divide it by 13. In no step there should be any remainder (you can simulate that you're guessing or thinking very hard about them). The end result is the number chosen initially.

For example for 439:

439439 (write it again, next to the number)

439439 / 7 = 62777

62777 / 11 = 5707

5707 / 13 = 439

Why does this work? Because 7 x 11 x 13 = 1001