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? – Olivier Grégoire Aug 28 '17 at 23:29
• @OlivierGrégoire You should know that your answer works for sure. – Sriotchilism O'Zaic Aug 28 '17 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? – Olivier Grégoire Aug 28 '17 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. – Sriotchilism O'Zaic Aug 28 '17 at 23:35

Java, by okx

Note: the original challenge to which this post answers has been deleted, it's however still accessible with the link to anyone having the privilege to see deleted answers. The explanations below include what the challenge was about.

Number: 18

The code is effectively looking for primes with the form 112n-2.

By this Wikipedia list, we know that the 20th largest known prime number has 2,900,832 digits. No prime with the form 112n-2 are in that list, so that digit number will be our limit.

All numbers of the form 112n-2 that have at most that many digits have this constraint: n < 22. Factordb tells us that 11222-2 has 4,367,918 digits. This is proof enough.

The code by okx limits us to n above 6.

So, let's do the list:

112n-2 is factorizable for n = 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20 and 21 (factors proofs are on factordb.com and wolfram alpha; factordb has some proofs that wolfram alpha hasn't and vice-versa).

The only value n for which we can't prove the factorization is 18 (factordb, WolframAlpha).

So (a) if there is a prime number of the form 112n-2 with n > 6, then (b) 6 < n < 22, and (c) I proved each number with such n is composite except for 18, so (d) the prime we're looking for has n = 18.

Note that I don't exclude that 11218-2 is composite. I haven't proved that that number is a prime: I only proved that if the OP thought about that number, it can only be 18. If that number is indeed a prime, congrats to okx for finding it :-)

However

There are no proof that 11218-2 is the only number, though. It's the only number in the range of numbers for which we can currently prove the primality.

So I don't exclude the fact that one day someone might prove that 11251-2 or 112124-2 is prime.

I therefore believe that the original entry by okx is invalid because there are no such proof that for n between 19 and the (231-1)231-1 (the theoretical limit of Java's BigInteger), there are no other primes.

• 11^(2^51) - 2 is divisible by 7. Or any odd n. – Leaky Nun Aug 29 '17 at 9:35
• Sorry guys, I bruteforced my way here. I haven't analyzed in details ;) – Olivier Grégoire Aug 29 '17 at 10:43
• @JollyJoker that's just from the binomial theorem: (10+1)^n = sum (nCr) 10^r – Leaky Nun Aug 29 '17 at 11:34
• Damn, the original challenge got deleted. Am I required to delete this answer as well? – Olivier Grégoire Aug 29 '17 at 14:23
• @OlivierGrégoire I think you should be okay. The solution took the same amount of effort, regardless of the original post. – Rɪᴋᴇʀ Aug 29 '17 at 19:11

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);
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&|@^

f =: monad define
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. – pppery Sep 20 at 23:43