# I'm thinking of a number (Robber's thread)

In this challenge cops will think of a positive integer. They will then write a program or function that outputs one value when provided the number as input and another value for all other positive integer inputs. Cops will then reveal the program in an answer keeping the number a secret. Robbers can crack an answer by finding the number.

Your job as robbers is to find that number. Once found you can make an answer here detailing the number and how you found it. You should link the original answer being cracked in your answer.

Your score will be the number of cracks with more being better.

• Are "hunches" good enough to post here, instead of definite proof? Aug 28, 2017 at 23:29
• @OlivierGrégoire You should know that your answer works for sure. Aug 28, 2017 at 23:31
• But I must know it, I don't have to prove it with the program given in the cops thread? Can I prove it otherwise, using math for instance? Aug 28, 2017 at 23:35
• @OlivierGrégoire Sure that's fine. As long as you know your answer is correct. You need not actually run the program if it takes too long. Aug 28, 2017 at 23:35

11

Try it online!

# Java, user902383

The secret number is 3141592

Explanation:

After expanding all the \u00xx escapes, you get:

public class Mango {
static void convert(String s){for(char c : s.toCharArray()){ System.out.print("\\u00"+Integer.toHexString(c));}}
public static void main(String[] args) {int x  = Integer.parseInt(args[0]);
double a= x/8.-392699;double b = Math.log10((int) (x/Math.PI+1))-6;
System.out.println((a/b==a/b?"Fail":"OK" ));
}}

(the convert method isn't used).

This computes some floating point math on the result, and then requires that a/b isn't equal to itself. The number for which that is true is nan, which is produced by 0/0. It turns out that if a is 0, then b is log10(0/pi + 1) which is also 0, so a has to be 0 and x has to be 392699*8.

# Python 3, user71546

def check(x):
if x < 0 or x >= 5754820589765829850934909 or pow(x, 18446744073709551616, 5754820589765829850934909) != 2093489574700401569580277 or x % 4 != 1:
return "No way ;-("
return "Cool B-)"

print(check(141421356237))

Try it online!

The number is 141421356237.

The other three numbers which satisfy the first two conditions are 1459265341309891512760823, 5754820589765688429578672, and 4295555248455938338174086.

### How I solved it

The gist of this challenge is to find the number that meets the following, given the prime p = 5754820589765829850934909 and a value a = 2093489574700401569580277:

• 0 <= x < p
• x ** (2 ** 64) % p == a
• x % 4 == 1

The second one can be rephrased to "find the modular square root of modular square root of ... (64 times) of a modulo p."

Since the given prime is 5 modulo 8, we can use the following formula from the above link (though I couldn't find the reference that supports it):

$v = (2a)^{(p-5)/8} \mod p$

$i = 2av^2 \mod p$

$r = av(i-1) \mod p$

$r' = p - r$

Then we have two output values r and r' for an input value a. But not every number has such a square root, so we have to check if r*r % p == a is actually met.

So I wrote a quick J script to find the 64th modular square roots.

p =: 5754820589765829850934909x
a =: 2093489574700401569580277x
powmod =: p&|@^

for. i.64 do.
v =: p | (2*a) powmod (p-5)%8
i =: p | 2*a*v*v
x =: p | a*v*i-1    NB. Apply the above formula
a =: (a=p|x*x) # x  NB. Filter by actually being the modular square root
a =: a, p-a         NB. Concat r with r'
a
end.
)

res =: f ''

Try it online!

res has the four values shown above; the last filtering by modulo 4 gives the answer.

• Link to "module square root" is dead. Sep 20, 2019 at 23:43