#!/usr/bin/php
<?php

define('MAX_POWER', 10);
define('MAX_DISTANCE', 99999);
ini_set('memory_limit', '2G');

# ---

function bcmul3($a,$b,$c) {
	return bcmul2($a,bcmul2($b,$c));
}

function bcabs($x) {
	return str_replace('-', '', $x);
}

function bcadd2($a,$b) {
	return gmp_add($a,$b);
}

function bcsub2($a,$b) {
	return gmp_sub($a,$b);
}

function bcmul2($a,$b) {
	return gmp_mul($a,$b);
}

function split_mul($z1, $z2) {
	// (a+bj)(c+dj) = (ac+bd) + (ad+bc)j
	$a = $z1[0];
	$b = $z1[1];
	$c = $z2[0];
	$d = $z2[1];
	$x = bcadd2(bcmul2($a,$c),bcmul2($b,$d));
	$y = bcadd2(bcmul2($a,$d),bcmul2($b,$c));
	return [$x, $y];
}

function split_int_power($split, $n) {
	assert($n >= 1);
	$res = $split;
	for ($p=2; $p<=$n; $p++) $res = split_mul($res, $split);
	return $res;
}

function split_is_immortal($split, $power) {
	$splitpow = split_int_power($split, $power);
	for ($i=0; $i<2; $i++) {
		$x1 = bcabs($split[$i]);
		$x2 = bcabs($splitpow[$i]);
		if (substr($x2, -strlen($x1)) != $x1) return false;
	}
	return $splitpow;
}

if (file_exists(__DIR__.'/savestate.txt')) {
	$start_distance = trim(file_get_contents(__DIR__.'/savestate.txt'));
} else {
	$start_distance = 0;
}

$progr = 0;

function _go($a, $b, $power, $distance, &$progr, &$found) {
	$splitpower = split_is_immortal([$a, $b], $power);
	if ($splitpower !== false) {
		$a_ = $splitpower[0];
		$b_ = $splitpower[1];
		if ($b!=0) {
			$str = "SPCP ";
		} else {
			$str = "REAL ";
		}
		$str .= "| Distance=$distance | ";
		$str .= "[$a + $b j] ^ $power = [$a_ + $b_ j]";
#		echo "$str\n";
		$found[] = $str;
	}
	#if (++$progr == 10000) {
	#       echo "(Dist=$distance) Processing ($a, $b) with power $power                 \r";
	#       $progr = 0;
	#}
}

for ($distance=$start_distance; $distance<=MAX_DISTANCE; $distance++) {
	$str = "--------- Distance: $distance ---------";
	//echo "                                                                              \r";
	echo "$str\n";
	$found = [ $str ];

	for ($power=2; $power<=MAX_POWER; $power++) {
		$a = $distance;
		for ($b=0; $b<$distance; $b++) {
			echo "\r".round(memory_get_usage()/1024/1024, 2)." MiB (".count($found)." found); ($a), $b                                ";
			_go($a, $b, $power, $distance, $progr, $found);
		}

		$b = $distance;
		for ($a=0; $a<=$distance; $a++) {
			echo "\r".round(memory_get_usage()/1024/1024, 2)." MiB (".count($found)." found); ($a), $b                                ";
			_go($a, $b, $power, $distance, $progr, $found);
		}
	}

	file_put_contents(__DIR__.'/result.txt', implode("\n",$found)."\n", FILE_APPEND);
	file_put_contents(__DIR__.'/savestate.txt', $distance+1);
}