Wednesday, January 26, 2011

Just a little bit nerdy

I have been accussed by colleagues of being nerdy and the traits that they ascribe to me are somewhere along the autism spectrum and it's true that I did the Autism Quotient test and scored 32 (the average man apparently scores 17).

And thus I shall embrace nerdiness today and answer the following vital question: "If you type all the powers of 2 from 2^0 to 2^16 on a standard telephone keypad, how many times do you type each number and what pattern does it make?".

Telephone keypad on the left, in the middle the number of times each key is pressed, and a simple shading to show the same data. At the bottom is a simple bar chart showing frequency for each key.
It's pleasing that 7 is only typed once (in 32,768).

martijn said...

I'm probably not the only one who wondered whether there is some kind of pattern in there, i.e. whether certain digits are more likely to appear in powers of two. There are two such 'patterns' to be expected:

- 0 is less likely to appear as it never occurs as a first digit;
- 2, 4, 6 and 8 are more likely to appear as they are the only possibilities for the last digit.

I wondered if there are more, so I ran a visualization if the occurrence of digits in the powers of 2 between 0 and n, with n growing. I 'corrected' these occurrences by adding n/10 to the occurrence of 0 and subtracting n/4 from the occurrences of the other even numbers.

It still seems 1 is more likely to occur and 9 least likely with 0 occurring about an average number of times. I expect this is a consequence of Benford's law.

Nick Barnes said...

If we allow N to get larger, leading digits will be weighted logarithmically, but that effect will diminish, and I'd be very surprised if the limit distribution is non-uniform.

Nick Barnes said...

Indeed, it all flattens out at large N. This code will lose all its formatting in this comment box, but should still work OK.
(defun hist (N)
(let ((counts (make-hash-table)))
(loop for i from 1 to N do
(let ((power (write-to-string (expt 2 i))))
(loop for c across power do
(incf (gethash c counts 0)))))
(let* ((results (loop for i from 0 to 9
collect (gethash (code-char (+ (char-code #\0) i)) counts 0)))
(max (apply 'max results))
(digits (+ 1 (ceiling (log max 10)))))
(format nil "http://chart.googleapis.com/chart?cht=bvg&chs=~dx150&chd=t:~{~d~^,~}&chds=0,~d&chxt=x,y&chxr=1,0,~d" (+ 350 (* digits 10)) results max max))))

For instance, (hist 10000) evaluates to http://chart.googleapis.com/chart?cht=bvg&chs=430x150&chd=t:1501917,1506478,1505995,1505195,1508431,1504063,1505333,1507073,1507850,1505670&chds=0,1508431&chxt=x,y&chxr=1,0,1508431

Martyloo said...

Can you post the code? :-)

Nick Barnes said...

That is the code.

martijn said...

You're right, Nick, about the leading digits not making any difference for N big enough. And what I said about Benford's law doesn't make any sense -- I just tried to explain behaviour I saw in my graphs that was explained by N not being large enough.

Can anyone prove that for N -> infty the distribution is logarithmic?

Nick Barnes said...

I don't have the chops to prove anything about this. Instinct tells me that the limit is uniformly distributed. I expect a proof strategy might be related to proofs about "normal numbers", an area about which little is known.

martijn said...

Sorry, I meant uniform, not logarithmic.

I'm fairly certain I can prove that at any given position (counted from the back) the occuring digits occur 'uniformly' -- I'd have to dig up some number theory though -- but I don't think that is enough for the proof.