No full ACK in SEPT

[dangermouse]

My solution was very bad, in the sense that I learn little about modulo arithmetic...
I just looked for fix points in range 0..7^7 which fullfilled the following equation:
(n = 2^n mod 7^7)
and found two points. One minus 3 was the solution...
The other fixpoint is 6254451_7.

The fixpoint property is required by the ACK solution, but I do not know how to determine the correct fixpoint, if I would have received 10000 of them instead of two.
So, I would be very interested in the official way on how to solve it.

[MatRush]

My solution was very bad, in the sense that I learn little about modulo arithmetic...
I just looked for fix points in range 0..7^7 which fullfilled the following equation:
(n = 2^n mod 7^7)
and found two points. One minus 3 was the solution...
The other fixpoint is 6254451_7.

The fixpoint property is required by the ACK solution, but I do not know how to determine the correct fixpoint, if I would have received 10000 of them instead of two.
So, I would be very interested in the official way on how to solve it.

I think this one may be need some number theory knowledge about euler function and euler's theorem and the Knuth's up-arrow notation, In fact, when a the n and m are bigger than 4, ack(n, m) % MOD is a constant.

[Redford]

Hi!
ack(7,7) = 2^2^2^2^2.... -3 (many many twos)
You have to calc 2^2^2^2^2.... -3 mod 7^7
Using Euler's theorem http://en.wikipedia.org/wiki/Euler%27s_theorem (a^phi(m) mod m = 1 when a and m are coprime) you can simplify this expression to:
2^(2^2^2^2.... mod phi(7^7)) mod 7^7, and now, the only problem is to calculate 2^2^2^2.... mod phi(7^7) = 2^2^2^2.... mod 2*3*7^6.
It's a bit harder, because "2^2^2^2...." and modulo (2*3*7^6) are not coprime. You can solve this using Chinese remainder theorem http://en.wikipedia.org/wiki/Chinese_remainder_theorem.
You can divide modulo into 2 and 3*7^6, calculate 2^2^2^2.... mod 2 (it's 0) and 2^2^2^2.... mod 3*7^6, and then construct the result (because 2 and 3*7^6 are coprime, you can use Chinese remainder theorem).
But now we still have something to solve: 2^2^2^2.... mod 3*7^6. Looks very similar to previous problem (recursion ). I've created function which takes modulo (as powers of 2,3 and 7) and returns 2^2^2^2^2.... mod argument.
I hope you've understood something, writing math symbols in plaintext is quite hard and ugly

[dangermouse]

Thx Redford for the clear explanation I put in my records for future reference...

[Hippo]

I used the same trick as for the decadic case ...
2^2^2^... modular exponentation using \phi (3^i*7^j) (i in {0,1}, j in {0,1,2,3,4,5,6,7} always leads to requirement of % 12*7^(j-1)) knowledge reaching 0 quickly ... so I have waited till 2^x % (12*7^7) stabilises.

Code: Select all

	public static void main(String args[]) {
		BigInteger t=BigInteger.ZERO;
		BigInteger m = new BigInteger("7").pow(7);
		BigInteger bm = m.multiply(new BigInteger("12"));
		for(int i=0;i<20;i++) {
			t=new BigInteger("2").modPow(t,bm);
			System.out.printf("\n"+t.toString(7)+"("+t.mod(m).subtract(new BigInteger("3")).toString(7)+")");
		}
	}

[niteria]

I had a basic plan of attack with Euler Totient function and Chinese Remainder Theorem, but I was too lazy to code it, so I eventually found https://github.com/sasdf/ctf/tree/06ef8 ... v/bigmaffs.