#!/usr/bin/php
<?php

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

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

define('FIX_PAD',       12);
define('ONLY_IM',     true);
define('SHOW_RESULT', true);
define('SHOW_DIST',   true);
define('BEGIN_PROGR', 116000); // allows continuation of calculation
define('OUT_FILE', 'complex_power2_search.out');

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

if (BEGIN_PROGR == 0) {
	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";
}

for ($progress=BEGIN_PROGR; true; $progress++) {
	echo "Progress: $progress\r";

	$new_y = 0;
	$prog2 = $progress*2;

	for ($i=0; $i<$progress; $i++) {
		_go($i, $progress, $new_y, 'A'); # X<Y (this case is not possible? but I cannot proove it)
		_go($progress, $i, $new_y, 'B'); # X>Y
		$new_y += $prog2;
	}

	// This case is only possible if X=Y=0
	//_go($progress, $progress, $new_y, 'C');  # X=Y
}

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($x, $y, $new_y, $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;
	}

	// 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^...

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

	$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;

	$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";
}