Mathmatical Possibilities

Kudose

I'm not the greatest at math and I am hoping to catch a math wiz around here. 🙂

I've got a script which selects between 1 and 12 characters out of 65 possible.

How many unique hashes can be created?

Is it 65^12?

TIA!

Weedpacket

65¹² is the number of hashes that are exactly 12 characters long.

You want 65¹² + 65¹¹ + ... + 65¹ = S

S = n¹ + n² + n³ + n⁴ + ... n^m = n(1 + n¹ + n² + n³ + ... + n^(m-1))
S = n(1+S-n^m)
S = n+nS-n^(m+1)
S-nS = n-n^(m+1)
S(1-n) = n-n^(m+1)
S = (n^{(m+1)-n)/(n-1)}

n=65 and m=12, so

S = (65^{(12+1)-65)/(65-1)}
= 5776884204716739654540

NogDog

Weedpacket wrote:
...
S = (65^{(12+1)-65)/(65-1)}
= 5776884204716739654540

Or: roughly 25% more than the estimated age of the universe measured in ten-thousandths of a second. 🙂

Kudose

Thanks!

(I will need to read this a couple times 😉)

Elizabeth

Weedie, what would we do without you?

Weedpacket

Elizabeth wrote:
what would we do without you?

Said I to the youngest cat today when she piddled in the corner; her front in the litter tray, her rear ... not.

A wee observation is that the hashes less than twelve characters long only contribute about 1.5% of that total (only (65^{(11+1)-65)/(65-1),} in fact🙂). So it's debatable whether it's worth having them.

Elizabeth

Weedpacket wrote:
Said I to the youngest cat today when she piddled in the corner; her front in the litter tray, her rear ... not.

Hehe, my cat does that all the time... he also forgets that I fed him so continues to meow at me until I pretend to feed him again. Not the sharpest tool in the shed, that one.

bpat1434

My cat used to hide in the litter box.... would sleep there before she got used to us 🙁 Not the greatest feeling in the world: top soft as a feather, bottom all gritty ....

Weed, would you mind explaining that math? I'm pretty-good with it, but I'm losing it when you just introduce "S" into the second line:

S = n(1+S-n^m)

Also, correct me if I'm wrong, but if you have:
S(1-n) = ....

and you thus divide by (1-n) so you have:
S(1-n)/(1-n) = .....

Wouldn't you divide both sides by (1-n) so:

S(1-n)/(1-n) = (.....)/(1-n)

Kudose

Just in case anyone was wondering about the code, since we are programmers n all. 😉

/** create record **/
        $now = date("YmdHis");
        $remoteIP = (isset($_SERVER['HTTP_X_FORWARDED_FOR'])) ? $_SERVER['HTTP_X_FORWARDED_FOR'] : $_SERVER['REMOTE_ADDR'];
        srand((float)microtime() * 1000000);
        $chars = rand() % 12 + 1;
        $charmap = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 
                         'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 
                         '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '-', '_', '.');
        shuffle($charmap);
        $dest = '';
        do{
          for($i=1;$i<=$chars;$i++){
            $dest .= $charmap[array_rand($charmap)];
          }
        }while($DB->getRow("SELECT dest FROM ".DB_PREFIX."urltable WHERE dest='".$dest."' LIMIT 1"));

NogDog

Elizabeth wrote:
Hehe, my cat does that all the time... he also forgets that I fed him so continues to meow at me until I pretend to feed him again. Not the sharpest tool in the shed, that one.

Had a cat when I was in my teens that would meow at me to put fresh food in her dish. I'd go with her to where her food dish was - still with a fair amount of food in it - and just give it a 1-second stirring with my hand. At that point she'd dive in and happily start chomping away at it.

Now my dog Noggin, on the other hand, gets one cup of food in the morning and one in the evening, and the dish is empty within 30 seconds (tops) of the food being dumped into it. 🙂

dclamp

My friends cat only meows at ME when he is hungry. And if you say his name (Parker) then he will meow. After you feed him, he wont reply when you say his name...

Weedpacket

bpat1434 wrote:
Weed, would you mind explaining that math? I'm pretty-good with it, but I'm losing it when you just introduce "S" into the second line:

The second line is

Weedpacket wrote:
You want 65¹² + 65¹¹ + ... + 65¹ = S

More generally, the first line of that algebraic stuff starts:

S = n¹ + n² + n³ + n⁴ + ... n^m

It's just short for "the sum of the sequence of powers of n from 1 to m". n being the number of characters in the alphabet, and m the maximum length. I think it safe to assume that for our purposes both will be nonzero. In fact, I'm assuming n>1. Otherwise the rest of the working will be invalid, but findint the correct answer would be trivial anyway.
As for the line after that:

S = n/i

Say m=4. Then S = n^{1+n^{2+n^{3+n^4.}}} You can divide through by n to find that

n^{1+n^{2+n^3+n⁴}} = n/i.

Apart from the multiplication by n, the only difference between the two sides is that one has a term n⁰ and the other has a term n^4. The left-hand side I've called S. If I take S, subtract the n^4, add n^0, and multiply the whole lot by n, I get the right hand side. Hence

S = n/i

Or m instead of 4, in general.

bpat1434 wrote:
Wouldn't you divide both sides by (1-n) so:

S(1-n)/(1-n) = (.....)/(1-n)

Yep, I'm negating the denominator on the right there. But that's okay, because I'm negating the numerator, too: n-n^(m+1) is a negative number. So is 1-n; when I wrote that line I just automatically multiplied the fraction by (-1/-1).

Oh, she knows what the litter tray is for, and she does try so hard. But she's still not clear just how to use it. What thought process led to her using the bath plughole to poo, on the other hand....

Weedpacket

Kudose wrote:

srand((float)microtime() * 1000000);

I take it all back: in that case the number of possible hashes is 1,000,000, because that's how many possible random seeds there are from that generator (you do know that [man]srand[/man] isn't required any more?)

Using the default seeding mechanism would help, but not on Windows. Windows's rand() is already limited to 15 bits, which means that all seeds (and all output values) are limited to between 0 and 32767 inclusive. It's a linear-congruential generator, too; there's effectively only one sequence, from which you have a choice of 32768 different starting points.

$t = array_fill(0, 32768, 0);
for($i=0; $i<32768; ++$i)
{
	$t[rand()]++;
}
echo join("", $t);

Being linear-congruential, if you know the output at one point, you can determine future points. 3611 is always followed by 27576 is always followed by 7569, and what srand() does is let you pick your starting point.

srand(42); echo rand(),"\t",rand(),"\n";
srand(3611); echo rand(),"\t",rand(),"\n";
srand(27576); echo rand(),"\t",rand(),"\n";

$im = imagecreate(32768>>4, 32768>>4);
$yellow = imagecolorallocate($im, 255,255,0);
$black = imagecolorallocate($im, 0,0,0);
imagefilledrectangle($im, 0,0,32768>>4, 32768>>4, $black);

$y = 0;
for($t=0; $t<100000; ++$t)
{
	$x = rand();
	imagesetpixel($im, $x>>4, $y>>4, $yellow);
	$y = $x;
}

imagepng($im, 'phaseplot.png');

The Mersenne Twister, on the other hand, has 2,147,483,647 different starting values and hence at most that many different sequences. The Mersenne Twister has a much longer period before it starts repeating because it maintains a buffer of previous values and uses those when generating the next; but PHP does not support any initialisation beyond a single 31-bit value. But because of that buffer, just knowing the value at one point is insufficient to predict the rest of the sequence.

$im = imagecreate(32768>>4, 32768>>4);
$yellow = imagecolorallocate($im, 255,255,0);
$black = imagecolorallocate($im, 0,0,0);
imagefilledrectangle($im, 0,0,32768>>4, 32768>>4, $black);

$y = 0;
for($t=0; $t<100000; ++$t)
{
	$x = mt_rand();
	imagesetpixel($im, $x>>20, $y>>20, $yellow);
	$y = $x;
}

imagepng($im, 'mt_phaseplot.png');

Kudose

Weedpacket wrote:
you do know that [man]srand[/man] isn't required any more?

I do now. 🙂