math combinatorics

gistfile1.php

<?php
/*
There are 299 numbers that contain 14 between 1 to 10,000 (not 300, because 1414 will be counted as 1)
How many numbers contain 14 between 1 to 10,000,000 ?
How many numbers contain 14 between 1 to 10,000,000,000 ?

ref:
https://www.mathsisfun.com/combinatorics/combinations-permutations.html
http://stackoverflow.com/questions/28182960/counting-same-containt-number-from-range-number-without-loop-in-ruby
http://math.stackexchange.com/questions/924399/how-many-integers-between-1-and-10n-contain-14au-cs244b/
http://math.stackexchange.com/questions/388554/how-many-numbers-between-1-and-10-000-000-dont-have-the-sequence-12-inclusion

Example :
	1000000
	 XXXX14	-> pow 10, 4
	 XXX14X	-> pow 10, 4
	 XX14XX	-> pow 10, 4
	 X14XXX	-> pow 10, 4
	 14XXXX	-> pow 10, 4
			-> Max Possible = 50000

	Overlaps: combination
	1000000
	 XX1414	-> pow 10, 2
	 X14X14	-> pow 10, 2
	 X1414X	-> pow 10, 2
	 14XX14	-> pow 10, 2
	 14X14X	-> pow 10, 2
	 14XX14 -> pow 10, 2
	 		-> overlaps = 600

	Overlaps: combination
	1000000
	 141414	-> 1 x

	Result: 50000 - (600 - 1) = 49401
*/

	// for verifying only.
	function docount($n) {
		if ($n < 2) {
			return;
		}
		return pow(10, $n) - (pow((5 + sqrt(24)), $n + 1) / (2 * sqrt(24))) + (pow(5 - sqrt(24), $n + 1) / (2 * sqrt(24)));
	}

	$loop = 10;
	$gi = 2;
	for ($i = $gi ; $i <= $loop; $i++) {
		echo "n = " . $i . "\t: " . docount($i) . "\n";
	}
	echo "\n";

	for ($i = $gi ; $i <= $loop; $i++) {
		echo "n = " . $i . "\t: " . combinationCount($i) . "\n";
	//	echo "n = " . $i . "\t: " . manualhard($i) . "\n";
	}

	function combinationCount($n) {
		if ($n < 1)
			return 0;

		$max = (($n - 1) * pow(10, ($n - 2)));
		$reduce = 0;
		for ($i = 2; $i <= $n; $i++) {
			if ($i % 2 == 0 ) {
				$reduce = $reduce + getOverlapse($n, $i);
			}else {
				$reduce = $reduce - getOverlapse($n, $i);
			}
		}
		// Total possible - overlaps of (2nd - 3rd + 4th - 5th ...)
		return $max - $reduce;
	}

	function getOverlapse($n, $over){
		$spot = $over;
		$ex = $n - ($spot * 2);
		$up =  $ex + $spot;
		if ($over = 2) {
			$down = $spot;
		}else{
			$down = $up - $spot;
		}
		return ($ex >= 0) ? combinatorics($up, $down) * pow(10, $ex) : 0;
	}

	function combinatorics($up, $down) {
		// try to use built in php factorial function
		if (function_exists("gmp_fact")) {
			return gmp_fact($up) / (gmp_fact ($down) * gmp_fact($up - $down));
		}
		return recurFactorial($up) / (recurFactorial($down) * recurFactorial($up - $down));
	}

	function recurFactorial($i){
		if ($i <= 1) {
			return 1;
		}
		return $i * recurFactorial($i - 1);
	}

	$memo = array();
	// Manual straigtforward loop and compare
	// very* slow on big number
	function manualhard($n) {
		global $memo;
		if ($n < 2) {
			return;
		}
		$max = pow(10, $n);
		$i = 2;
		$match = "14";
		$occur = 0;

		if (!empty($memo)){
			if (isset($memo[$n]['key'])) {
				return $memo[$n]['key'];
			}else {
				for ($j = $n - 1; $j > 0; $j--) {
					if (isset($memo[$j])) {
						$i = $memo[$j]['number'] +  1; //pow(10, $j); + 1;
						$occur = $memo[$j]['key'];
						break;
					}
				}
			}
		}
		for ($i ; $i <= $max; $i++) {
			if (substr_count((string)$i, $match) >= 1) {
				$occur++;
			}
		}
		$memo[$n]['key'] = $occur;
		$memo[$n]['number'] = $max;
		return $occur;
	}

/*	Output
	n = 2   : 1
	n = 3   : 20
	n = 4   : 299
	n = 5   : 3970
	n = 6   : 49401
	n = 7   : 590040
	n = 8   : 6850999
	n = 9   : 77919950
	n = 10  : 872348501

	n = 2   : 1
	n = 3   : 20
	n = 4   : 299
	n = 5   : 3970
	n = 6   : 49401
	n = 7   : 590040
	n = 8   : 6850999
	n = 9   : 77919950
	n = 10  : 872348501
*/

?>