Τρίτη 9 Μαΐου 2017

The colour of numbers: visions of our mathematical universe | Science | The Guardian

The colour of numbers: visions of our mathematical universe | Science | The Guardian

The 3n+1 problem and Benford’s law

The 3n+1 problem and Benford’s law



The 3n+1 problem and Benford’s law

This
is the third, and last, of a series of posts on Benford’s law, this
time looking at a famous open problem in computer science, the 3n + 1 problem, also known as the Collatz conjecture.

Start with a positive integer n. Compute 3n
+ 1 and divide by 2 repeatedly until you get an odd number. Then repeat
the process. For example, suppose we start with 13. We get 3*13+1 = 40,
and 40/8 = 5, so 5 is the next term in the sequence. 5*3 + 1 is 16,
which is a power of 2, so we get down to 1.

Does this process always reach 1? So far nobody has found a proof or a counterexample.

If you pick a large starting number n
at random, it appears that not only will the sequence terminate, the
values produced by the sequence approximately follow Benford’s law (source). If you’re unfamiliar with Benford’s law, please see the first post in this series.

Here’s some Python code to play with this.

from math import log10, floor

def leading_digit(x):
    y = log10(x) % 1
    return int(floor(10**y))

# 3n+1 iteration
def iterates(seed):
    s = set()
    n = seed
    while n > 1:
        n = 3*n + 1
        while n % 2 == 0:
            n = n / 2
        s.add(n)
    return s
Let’s save the iterates starting with a large starting value:

it = iterates(378357768968665902923668054558637)
Here’s what we get and what we would expect from Benford’s law:

|---------------+----------+-----------|
| Leading digit | Observed | Predicted |
|---------------+----------+-----------|
|             1 |       46 |        53 |
|             2 |       26 |        31 |
|             3 |       29 |        22 |
|             4 |       16 |        17 |
|             5 |       24 |        14 |
|             6 |        8 |        12 |
|             7 |       12 |        10 |
|             8 |        9 |         9 |
|             9 |        7 |         8 |
|---------------+----------+-----------|
We get a chi-square of 12.88 (p = 0.116) and so we get a reasonable fit.

Here’s another run with a different starting point.

it = iterates(243963882982396137355964322146256)
which produces

|---------------+----------+-----------|
| Leading digit | Observed | Predicted |
|---------------+----------+-----------|
|             1 |       44 |        41 |
|             2 |       22 |        24 |
|             3 |       15 |        17 |
|             4 |       12 |        13 |
|             5 |       11 |        11 |
|             6 |        9 |         9 |
|             7 |       11 |         8 |
|             8 |        6 |         7 |
|             9 |        7 |         6 |
|---------------+----------+-----------|
This has a chi-square value of 2.166 (p = 0.975) which is an even better fit.

4-LED Octal Clock Demands Colorful Math | Hackaday

4-LED Octal Clock Demands Colorful Math | Hackaday














4-LED Octal Clock Demands Colorful Math



We’ve all seen LED clocks where RGB LEDs are used to display
time. It seems like the simpler the interface, the more likely you’d
need to do math to figure out the time. This Octal Clock by
[Alex Kurrasch] proves the point by using only four LEDs: the top two
show hours and minutes, and the bottom two LEDs are multipliers.


Using octal numbering,
[Alex] translates the data using a Venn diagram of color mixing. The
mapping uses 1 as red, 2 as green, followed by yellow, blue, magenta,
and cyan. It ends with 7 as white (all on) and 0 as black (all off).


As the time changes, a fading algorithm changes the display to match.
He offers the time of 7:38pm as an example in the grid shown here.
Base-8 math is provided; don’t worry, you’ll get really good at this if
you make your own wristwatch version… people will learn to never ask you about the time.


The clock uses a ATMega64 running assembly language firmware with a
DS1306E+ RTC chip keeping track of time. The enclosure is cool too;
[Alex] milled the case out of mahogany and the front and back plates are
anodized aluminum. The unique looking diffusers on the LEDs are
actually paraffin, a trick that [Elliot Williams] mentioned in his recent article on diffuser materials.


Posted in clock hacksTagged , , ,