#!/usr/bin/php
<?php

// ATTENTION: THIS OPTIMIZED SCRIPT VARIANT ONLY WORKS WITH BASE 10, POWER 2

# -------------------------------------------------

define('FIX_PAD',       18);
define('ONLY_IM',     true);
define('SHOW_RESULT', true);
define('SHOW_DIST',   true);
define('CHECKED_LOOKUP_READ',  true); // true = Much faster. Requires previous LOOKUP_WRITE,
define('CHECKED_LOOKUP_WRITE', true); // true = Prevent that a check is made more than one time. Requires much memory
define('CHECKED_LOOKUP_SAVE',  false); // true = Increases size of SAV file, but keeps performance after restart of the program
define('CHECKED_LOOKUP_SIZELIMIT', 10); // X+"/"+Y
define('FIXED_X', 9959106445313);
define('OUT_FILE', 'complex_power2_search_hyperspeed.out');
define('SAV_FILE', 'complex_power2_search_hyperspeed.sav');
define('SAV_FILE_EXT', 'complex_power2_search_hyperspeed_fixed_x.sav');
define('SAV_FILE_EXT_AUTOSAVE_INTERVAL', 100000);

# -------------------------------------------------

if (file_exists(SAV_FILE)) {
	list($found_x, $found_y, $checked, $found) = unserialize(file_get_contents(SAV_FILE));
} else {
	$found_x = array();
	$found_y = array();
	$checked = array();
	$found = array();
	echo "COMPLEX IMMORTAL NUMBER SEARCH 1.0\n";
	echo "\n";
	echo "Parameters:  Min base     = 10\n";
	echo "             Max base     = 10\n";
	echo "             Min power    = 2\n";
	echo "             Max power    = 2\n";
	echo "             Only Im(z)>0 = ".(ONLY_IM ? 'Yes' : 'No')."\n";
	echo "\n";
}

if (file_exists(SAV_FILE_EXT)) {
	$data = unserialize(file_get_contents(SAV_FILE_EXT));
	if (isset($data[FIXED_X])) {
		list($y, $found_y_maxy) = $data[FIXED_X];
	} else {
		$y = 0;
		$found_y_maxy = array();
	}
} else {
	$y = 0;
	$found_y_maxy = array();
}

while (true) {
	$something_found = false;

	if ($y%10000 == 0) echo "Round: $y          \r";

	if (_go($y, FIXED_X, $y, null, 'A')) $something_found = true;

	foreach ($found_y as $y_suffix) {
		if (!isset($found_y_maxy[$y_suffix]) || ($found_y_maxy[$y_suffix] < $y)) {
			if (_go($y, FIXED_X, $y.$y_suffix, null, 'a')) $something_found = true;
			$found_y_maxy[$y_suffix] = $y; // <-- this avoids that the everything needs to be checked again just because something was added to $found_x
		}
	}

	$y++;
	if ($something_found) $y = 0; // Restart, because the $found_x parameter has been changed!

	if ($y%SAV_FILE_EXT_AUTOSAVE_INTERVAL == 0) {
		file_put_contents(SAV_FILE_EXT, serialize(array('LastUsedX' => FIXED_X, FIXED_X => array($y, $found_y_maxy))));
	}
}

function endswith($string, $test) {
	// https://stackoverflow.com/questions/619610/whats-the-most-efficient-test-of-whether-a-php-string-ends-with-another-string?lq=1
	$strlen = strlen($string);
	$testlen = strlen($test);
	#if ($testlen > $strlen) return false;
	return substr_compare($string, $test, $strlen - $testlen, $testlen) === 0;
}

function _go($round, $x, $y, $new_y=null, $info='') {
	if ($y%2 == 1) return; // y must be even because "2xy === y"

	// For Base 10 power 2, X can only end with 3 or 8
	// 2*x*y        == y
	// 2*3*2 ==  12 == 2
	// 2*3*4 ==  24 == 4
	// 2*3*6 ==  36 == 6
	// 2*3*8 ==  48 == 8
	// 2*8*2 ==  32 == 2
	// 2*8*4 ==  64 == 4
	// 2*8*6 ==  96 == 6
	// 2*8*8 == 128 == 8
	if (ONLY_IM) {
		$last_digit = substr($x,-1);
		if (($last_digit != '3') && ($last_digit != '8')) return;
	}

	$x = ltrim($x, "0");
	$y = ltrim($y, "0");

	global $checked;
	$search_key = $x.'/'.$y;
	if (is_null(CHECKED_LOOKUP_SIZELIMIT) || (strlen($search_key) <= CHECKED_LOOKUP_SIZELIMIT)) {
		if (CHECKED_LOOKUP_READ && isset($checked[$search_key])) return false;
		if (CHECKED_LOOKUP_WRITE) $checked[$search_key] = 1;
	}

#	echo "Round $round, Checking: (".$x." + ".$y."i)^2                            \r";

	// Power 2:
	// (x+yi)^2 = x^2 + 2xyi - y^2 = (x^2-y^2 + 2xyi)
	// Therefore:
	// (x+yi) is immortal if
	// (x^2-y^2)^2 === x^2-y^2 mod 2^...
	// (2xy)^2     === 2xy     mod 2^...

	if (is_null($new_y)) {
		$new_y = bcmul(bcmul($x,$y),2);
		#if ($new_y[0] == '-') $new_y = substr($new_y, 1);
	}
	if (($new_y == 0) && (ONLY_IM)) return false;
	if (!endswith($new_y,$y)) return false;

	$new_x = bcsub(bcmul($x,$x),bcmul($y,$y));
	#if ($new_x[0] == '-') $new_x = substr($new_x, 1);
	if (!endswith($new_x,$x)) return false;

#	echo "Round $round, Candidate: (".$x." + ".$y."i)^2                                \r";

	global $found;
	if (isset($found[$x.'/'.$y])) return false;
	$found[$x.'/'.$y] = 1;

	global $found_x;
	if (/* ($new_x != 0) && */(!in_array($x,$found_x))) $found_x[] = $x;
	global $found_y;
	if (/* ($new_y != 0) && */(!in_array($y,$found_y))) $found_y[] = $y;

	file_put_contents(SAV_FILE, serialize(array($found_x,$found_y,CHECKED_LOOKUP_SAVE ? $checked : array(),$found)));

	global $found_y_maxy;
	file_put_contents(SAV_FILE_EXT, serialize(array('LastUsedX' => FIXED_X, FIXED_X => array($round, $found_y_maxy))));

	$line = '';
	$dist = round(sqrt($x*$x + $y*$y));
	if (SHOW_DIST) $line .= "[".str_pad($dist,FIX_PAD,'0',STR_PAD_LEFT)."] ";
	$line .= "IMMORTAL($info): (".str_pad($x,FIX_PAD,' ',STR_PAD_LEFT)." + ".str_pad($y,FIX_PAD,' ',STR_PAD_LEFT)."i) ^ 2";
	if (SHOW_RESULT) $line .= " = (".$new_x." + ".$new_y."i)";
	$line .= "\n";
	file_put_contents(OUT_FILE, $line, FILE_APPEND);
	echo "\r$line";

	return true;
}