7
\$\begingroup\$

Cop's thread here

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.

\$\endgroup\$
  • \$\begingroup\$ Are "hunches" good enough to post here, instead of definite proof? \$\endgroup\$ – Olivier Grégoire Aug 28 '17 at 23:29
  • \$\begingroup\$ @OlivierGrégoire You should know that your answer works for sure. \$\endgroup\$ – Sriotchilism O'Zaic Aug 28 '17 at 23:31
  • \$\begingroup\$ 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? \$\endgroup\$ – Olivier Grégoire Aug 28 '17 at 23:35
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Sriotchilism O'Zaic Aug 28 '17 at 23:35

15 Answers 15

10
\$\begingroup\$

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.

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

Perl 6, by Ramillies

11

The function series($x) is simply the first 108 terms of the Taylor series for e^x evaluated at i*(x % 8*π). Since e^2πi = 1, this reduces to simply e^ix: the % 8*π serves only to bound the error of the truncated series.

The function integrates the provided Callable in the interval [0,2π] using the trapezoid method. The integrand in question is (e^ix)^11/(e^inx), or simply e^(11-n)ix. This integrates to 0 in that interval for all n != 11. At n = 11, the integrand reduces to simply 1. Hence the answer is 11, and the desired output is 6.28.

While 11 is the only answer in theory, the sampling in the integral is imperfect. Consequently, any integer of the form 87931k+11 should work.

\$\endgroup\$
  • \$\begingroup\$ Very nicely done! You surprised me with the last paragraph however. I'll put it to some thought. \$\endgroup\$ – Ramillies Aug 29 '17 at 9:35
  • \$\begingroup\$ Ah, I now see the problem. I'm afraid I can't remove it however (even if I use intervals of different widths, you would use the product of the widths as a coefficient for your k)... Thanks for pointing it out. \$\endgroup\$ – Ramillies Aug 29 '17 at 9:49
8
\$\begingroup\$

Python 3, Erik Brody Dreyer

Number: 105263157894736842

Try it online!


How?

Everyone's favorite tool: OEIS!

  1. Go to oeis.org
  2. Search "last digit first doubles number"
  3. Find Entry A087502 entitled

    Smallest positive integer which when written in base n is doubled when the last digit is put first.

  4. Find the base 10 entry (105263157894736842)
  5. Confirm it works
\$\endgroup\$
  • 1
    \$\begingroup\$ Can't comment on Erik's post due to lack of rep. Welp, can only hope he sees this :) \$\endgroup\$ – sonar235 Aug 29 '17 at 0:47
  • \$\begingroup\$ Not sure if I would have thought of OEIS in this case, but just a few days ago I saw this \$\endgroup\$ – Christian Sievers Aug 29 '17 at 14:14
8
\$\begingroup\$

Tampio, fergusq

Number: 27

The program prints nolla for 27 and "1" negatiivisena for all other inputs. It times out on TIO, unfortunately, but works offline.

Whew, this was a fun one to work through. Wiktionary and this Finnish dictionary I found online actually helped a surprising amount, as a lot of Tampio syntax relies on inflection.

I first tried translating the program into Haskell-like pseudocode, but the "case system" of Tempio and how function calls worked kept tripping me up. Eventually, I ended up running all of the code from the definition of sata downward, which gave me surprisingly easily that sata == 55, and funktio wasn't difficult to reverse engineer from there as it was simple arithmetic that could be deduced from trial and error.

\$\endgroup\$
  • \$\begingroup\$ Can someone help me comment this on the original post, by the way? My rep is way too low for that - thanks! \$\endgroup\$ – Rin's Fourier transform Aug 29 '17 at 16:35
  • \$\begingroup\$ I've left a comment on the original. \$\endgroup\$ – Sriotchilism O'Zaic Aug 29 '17 at 16:37
  • \$\begingroup\$ @WheatWizard thanks! \$\endgroup\$ – Rin's Fourier transform Aug 29 '17 at 16:39
7
\$\begingroup\$

JavaScript, by Eli R

The number is 7464822360768511

I first disabled the anti-debugging function (by overwriting Function.prototype.constructor to a function with evals any code except debugger) then debugged the guess function by stepping into it.

From what I understood the guess function initializes a random number generator on a fixed seed then generate a random number and compare it to the input. As the input isn't used in the random number generation it can be ignored allowing to skip directly to the result.

\$\endgroup\$
  • \$\begingroup\$ Amazing job. That's exactly how it works. \$\endgroup\$ – Eli Richardson Aug 29 '17 at 15:03
5
\$\begingroup\$

Jelly, Erik the Outgolfer's answer

Number: 134

The following program:

5ȷ2_c⁼“ḍtṚøWoḂRf¦ẓ)ṿẒƓSÑÞ=v7&ðþạẆ®GȯżʠṬƑḋɓḋ⁼Ụ9ḌṢE¹’

can be cracked using the number 134. This outputs 0 for all numbers except for 134, which gives 1.

Try it online!


How did I find it?

TBH, I have no idea how it works. I have added ǀG at the end and mapped over [1...1000] to see where the 1 is. Then, I ran script to count the number of zeros before the 1.

\$\endgroup\$
  • \$\begingroup\$ This just checks that (500-x) choose (x) is equal to 11087887200298332182662619677215658902328839774316188391031942332464244226619146288405430113510542767630, which it is for x=134 (as you found). \$\endgroup\$ – fireflame241 Aug 29 '17 at 3:01
5
\$\begingroup\$

Ly, LyricLy

Answer: 239

I already wrote two Ly programs, so this wasn't too difficult. I think I would have somehow used the result from the loop in case someone tries to remove it. BTW, the fragment nI means that it doesn't always terminate successfully.

\$\endgroup\$
5
\$\begingroup\$

Python 2, Sisyphus

print~~[all([c[1](c[0](l))==h and c[0](l)[p]==c[0](p^q) for c in [(str,len)] for o in [2] for h in [(o*o*o+o/o)**o] for p,q in [(60,59),(40,44),(19,20),(63,58),(61,53),(12,10),(43,42),(1,3),(35,33),(37,45),(17,18),(32,35),(20,16),(22,30),(45,43),(48,53),(58,59),(79,75),(68,77)]] + [{i+1 for i in f(r[5])}=={j(i) for j in [q[3]] for i in l} for q in [(range,zip,str,int)] for r in [[3,1,4,1,5,9]] for g in [q[1]] for s in [[p(l)[i:i+r[5]] for p in [q[2]] for i in [r[5]*u for f in [q[0]] for u in f(r[5])]]] for l in s + g(*s) + [[z for y in [s[aprint~~[all([c[1](c[0](l))==h and c[0](l)[p]==c[0](p^q) for c in [(str,len)] for o in [2] for h in [(o*o*o+o/o)**o] for p,q in [(60,59),(40,44),(19,20),(63,58),(61,53),(12,10),(43,42),(1,3),(35,33),(37,45),(17,18),(32,35),(20,16),(22,30),(45,43),(48,53),(58,59),(79,75),(68,77)]] + [{i+1 for i in f(r[5])}=={j(i) for j in [q[3]] for i in l} for q in [(range,zip,str,int)] for r in [[3,1,4,1,5,9]] for g in [q[1]] for s in [[p(l)[i:i+r[5]] for p in [q[2]] for i in [r[5]*u for f in [q[0]] for u in f(r[5])]]] for l in s + g(*s) + [[z for y in [s[i+a][j:j+r[0]] for g in [q[0]] for a in g(r[0])] for z in y] for k in [[w*r[0] for i in [q[0]] for w in i(r[0])]] for i in k for j in k] for f in [q[0]]]) for l in [int(raw_input())]][0]

Try it online!

Answer:

126437958895621473374985126457193862983246517612578394269314785548769231731852649

Explanation

Slightly less convoluted:

print~~[all(
	[len(str(l))==81 and str(l)[p]==str(p^q)
		for p,q in [(60,59),(40,44),(19,20),(63,58),(61,53),(12,10),(43,42),(1,3),(35,33),(37,45),(17,18),(32,35),(20,16),(22,30),(45,43),(48,53),(58,59),(79,75),(68,77)]
	]
	+
	[{i+1 for i in range(9)}=={int(i) for i in l}
		for s in [[str(l)[9*u:9*u+9] for u in range(9)]]
			for l in s + zip(*s) + [[z for y in [s[i+a][j:j+3] for a in range(3)] for z in y] for k in [[w*3 for w in range(3)]] for i in k for j in k]]) for l in [int(raw_input())]][0]

Try it online!

Firstly, this part:

[len(str(l))==81 and str(l)[p]==str(p^q)
        for p,q in [(60,59),(40,44),(19,20),(63,58),(61,53),(12,10),(43,42),(1,3),(35,33),(37,45),(17,18),(32,35),(20,16),(22,30),(45,43),(48,53),(58,59),(79,75),(68,77)]
]

checks if the sudoku is in the following form:

.2.|...|...
...|6..|..3
.74|.8.|...
-----------
...|..3|..2
.8.|.4.|.1.
6..|5..|...
-----------
...|.1.|78.
5..|..9|...
...|...|.4.

Then this part checks for validity:

[{i+1 for i in range(9)}=={int(i) for i in l}
        for s in [[str(l)[9*u:9*u+9] for u in range(9)]]
            for l in s + zip(*s) + [[z for y in [s[a][j:j+3] for a in range(3)] for z in y] for k in [[w*3 for w in range(3)]] for i in k for j in k]]
\$\endgroup\$
3
\$\begingroup\$

Pyth, Mr. Xcoder

hqQl+r@G7hZ@c." y|çEC#nZÙ¦Y;åê½9{ü/ãѪ#¤
ØìjX\"¦Hó¤Ê#§T£®úåâ«B'3£zÞz~Уë"\,a67Cr@G7hZ

Try it here. Number: 9

\$\endgroup\$
  • \$\begingroup\$ Well done! It lived long \$\endgroup\$ – Mr. Xcoder Aug 28 '17 at 18:00
  • \$\begingroup\$ @Mr.Xcoder I just removed the hqQ part :p \$\endgroup\$ – Erik the Outgolfer Aug 28 '17 at 18:06
  • \$\begingroup\$ That's weird. I tried 9 but it didn't work. That was before it was temporarily deleted, though, so it may not originally have been 9. \$\endgroup\$ – Shaggy Aug 28 '17 at 19:00
  • \$\begingroup\$ @Shaggy Me too, but after it was undeleted. \$\endgroup\$ – Erik the Outgolfer Aug 28 '17 at 19:03
3
\$\begingroup\$

Swift 3, TheIOSCoder

Number: 387849.

This returns 222 for the number above, and 212 for others.

Test Here.


How?

The relation is quite obvious: .pi*123456.0 multiplies 3.1415... by 123456.0 and converts it to an Integer. This means it is equal to 387848. Then, it checks if the parameter equals the number above incremented by 1 (n==1+...). The value is 387848 + 1, which is 387849...

\$\endgroup\$
3
\$\begingroup\$

Java, Sleafar

23

The program traces n iterations of a fractal, and checks whether a specific point is removed in the nth iteration. In each iteration, each segment is replaced by eight smaller segments in the following pattern:

  +
  |
+-+
|
+-+-+
    |
  +-+
  |
  +

Since no points are ever added to the line y=.5 after the first iteration, I only had to handle the set of points included along this line. This set is similar to the construction of the Cantor set, but with the middle half removed instead of the middle third.

The program I used to crack it:

import java.math.BigDecimal;

public class Main {

        public static int f(BigDecimal x) {
                BigDecimal[] result = x.divideAndRemainder(BigDecimal.ONE);
                if (result[0].compareTo(BigDecimal.ZERO) == 0 || result[0].compareTo(BigDecimal.valueOf(3)) == 0) {
                        return 1+f(result[1].multiply(BigDecimal.valueOf(4)));
                }
                return 0;
        }

	public static void main(String[] args) {
		BigDecimal x = new BigDecimal(args[0]);
		System.out.println(f(x));
	}
}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This is correct, congratulations! \$\endgroup\$ – Sleafar Aug 30 '17 at 6:17
2
\$\begingroup\$

Haskell, flawr

I think the number is 12018.

I found it by defining in PARI/GP f(x,k)=1/x^2-1/x^(2-1/k) and g(k)=sumpos(x=1,f(x,k))-sumpos(x=12345679,f(x,k)) and some binary searching.

I don't like that one could trivially transform the program into one that returns the number and uses the same time and memory as the original program needs for any input.

\$\endgroup\$
2
\$\begingroup\$

Brain-Flak, Nitrodon

The number is:

1574

Try it online!

Here's the program I use to crack it

n!(0:_)=n
n!a=(n+1)!zipWith(+)a(tail a++[0])
main=print$0![45646,253224,392678,8676,-24]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Link to "module square root" is dead. \$\endgroup\$ – pppery Sep 20 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.