Somewhat interesting, 123456789 * 8 is 987654312 (the last two digits are swapped). This holds for other bases as well: 0x123456789ABCDEF * 14 is 0xFEDCBA987654312.
Also, adding 123456789 to itself eight times on an abacus is a nice exercise, and it's easy to visually control the end result.
I also went about looking at the difference rather than the order. In the hexadecimal case, the difference is 15 (0xEF vs 0x12). I thought, then, that for any base B with ascending digits A and descending digits D, (D-(B-1))/A=B-2.
For binary, it looks like (1-(b-1))/1=b-10 or (1-(2-1))/1=2-2=0 in decimal.
For trinary, it looks like (21-(b-1))/12=b-2 or (7-(3-1))/5=5/5=1 in decimal.
For quaternary, it looks like (321-(b-1))/123=b-2 or (57-(4-1))/27=54/27=2 in decimal.
Essentially and perhaps unsurprisingly, the size of the slices in the number pie get smaller the bigger the pie gets. In binary, the slice is the pie, which is why the division comes out to zero there.
This was by far the most interesting part to me. I've never considered that code and proofs can be so complementary. It would be great if someone did this for all math proofs!
"Why include a script rather than a proof? One reason is that the proof is straight-forward but tedious and the script is compact.
A more general reason that I give computational demonstrations of theorems is that programs are complementary to proofs. Programs and proofs are both subject to bugs, but they’re not likely to have the same bugs. And because programs made details explicit by necessity, a program might fill in gaps that aren’t sufficiently spelled out in a proof."
As a kid, I was marginally decent at competitive math. Not good like you think of kids who dominate those type of competitions at a high level, but like I could qualify for the state competition type good.
What I was actually good, or at least fast at, was TI-Basic, which was allowed in a lot of cases (though not all). Usually the problems were set up so you couldn’t find the solution using just the calculator, but if you had a couple of ideas and needed to choose between them you could sometimes cross off the wrong ones with a program.
The script the author gives isn’t a proof itself, unless the proposition is false, in which case a counter example always makes a great proof :p
I used to do the same thing. I'd scan for problems on the test amenable to computational approaches and either pull up one of my custom made programs or write one on the spot and let it churn in the background for a bit while I worked on other stuff without the calculator.
This is misleading in that the (Curry–Howard) correspondence is between proofs and the static typing of programs. A bug in a proof therefore corresponds to a bug in the static typing of a program (or to the type system of the programming language being unsound), not to any other program bug.
The point is to not be so tight, leaning on the correspondence. The fact that you’re coming at the problem differently (even that it’s a different problem, “for some” versus “for all”) is actually helpful. You’re less likely to make the same mistake in both.
There’s a technique for unit testing where you write the code in two languages. If you just used a compiler and were more confident about correspondence, that would miss the point. The point is to be of a different mind and using different tools.
The other replies are good, but let's add another one anyway.
0.987654321/0.123456789 = (1.11111111-x)/x = 1.11111111/x - 1 where x = 0.123456789
You can aproxímate 1.11111111 by 10/9 and aproxímate x = 0.123456789 using y = 0.123456789ABCD... = 0.123456789(10)(11)(12)(13)... that is a number in base 10 that is not written correctly and has digits that are greater than 9. I.E. y = sum_i>0 i/10^i
Now you can consider the function f(t) = t + 2 t^2 + 3 t^3 + 4 t^4 + ... = sum_i>0 i*t^i and y is just y=f(0.1).
And also consider an auxiliary function g(t) = t + t^2 + t^3 + t^4 + ... = sum_i>0 1*t^i . A nice property is that g(t)= 1/(1-t) when -1<t<1.
The problem with g is that it lacks the coefficients, but that can be solved taking the derivative. g'(t) = 1 + 2 t + 3 t^2 + 4 t^3 + ... Now the coefficients are shifted but it can be solved multiplying by t. So f(t)=t*g'(t).
So f(t) = t * (1/(1-t))' = t * (1/(1-t)^2) = t/(1-t)^2
Now add some error bounds using the Taylor method to get the difference between x and y, and also a bound for the difference between 1.11111111 an 10/9. It shoud take like 15 minutes to get all the details right, but I'm too lazy.
(As I said in another comment, all these series have a good convergence for |z|<1, so by standards methods of complex analysis all the series tricks are correct.)
An easier way to evaluate sum i/10^i is by squaring sum 1/10^i
If you multiply term by term every term has coefficient 1 of course. There are n terms with exponent n+1, made from the n sums of the first exponent and the second exponent.
Eg 1+5, 2+4, 3+3, 4+2, 5+1.
So (1/9)^2 = (sum 1/10^i)^2 = 1/10 sum i/10^i
The derivative trick is more useful generally, but this method gets you the solution to 0.12345678.. in an quick way that's also easier to justify that it works.
I remember seeing that (14787 + 36989) / 2 would produce 25888, in that the mean of geometric shape traced by the two sequences would average out in the middle like that
the design of a keypad... it unintentionally contains these elegant mathematical relationships.
i call this phenomena: outcomes of human creations can be "funny and odd", and everybody understand that eventually there will be always something unpredictable.
Great, now I'm getting Carrot Top flashbacks. "Dial right down the center of the phone!"
For non-Americans and/or those too young to remember when landline service was still dominant, in the 90s and early 2000s AT&T ran a collect-call service accessible through the number 1-800-CALL-ATT (1-800-225-5288) and promoted it with ads featuring comedian Carrot Top. And if you don't know who Carrot Top is, maybe that's for the best.
Interesting how it works out but I don't think it is anywhere close to as intuitive as the parent comment implies. The way its phrased made me feel a bit dumb because I didn't get it right away, but in retrospect I don't think anyone would reasonably get it without context.
It actually skips the 8 in its repeating decimal. It’s better to think of 1/9^2 as the infinite sum of k * 10^-k for all positive integers k. The 8 gets skipped because you have something like ...789(10)(11)... where the 1 from the “10” and “11” digits carry over, increment the 9 digit causing another carry, so the 8 becomes a 9.
.123456... = x + 2 x^2 + 3 x^3 + ... with x = 1/10.
Then you have
(x + 2 x^2 + 3 x^3 + ...) = (x + x^2 + x^3 + x^4 + ...) + (x^2 + x^3 + x^4 + x^5 + ...) + (x^3 + x^4 + x^5 + x^6 + ...)
(count the number of occurrences of each power of x^n on the right-hand side)
and from the sum of a geometric series the RHS is x/(1-x) + x^2/(1-x) + x^3/(1-x) + ..., which itself is a geometric series and works out to x/(1-x)^2. Then put in x = 1/10 to get 10/81.
If you set x = 0.123456..., then multiplying it by (10 - 1) gives 9x = 1.111111..., and multiplying it by (10 - 1) again gives 81x = 10, or x = 10/81. I’m not writing things formally here but that’s the rough idea, and you can do the same procedure with 0.987654... to get 80/81.
So 987,654,321 + 2 x 123,456,789 \approx 10 x 123,456,789
Thus 987,654,321 / 123,456,789 \approx 8.
If you squint you can see how it would work similarly in other bases. Add the 123... equivalent once to get the base-independent series of 1's, add a second time to get the base-independent 123...0.
Also, adding 123456789 to itself eight times on an abacus is a nice exercise, and it's easy to visually control the end result.
base 16: 123456789ABCDEF~16 * (16-2) + 16 - 1 = FEDCBA987654321~16
base 10: 123456789~10 * (10-2) + 10 - 1 = 987654321~10
base 9: 12345678~9 * (9-2) + 9 - 1 = 87654321~9
base 8: 1234567~8 * (8-2) + 8 - 1 = 7654321~8
base 7: 123456~7 * (7-2) + 7 - 1 = 654321~7
base 6: 12345~6 * (6-2) + 6 - 1 = 54321~6
and so on..
or more generally:
base n: sequence * (n - 2) + n - 1
They are also +9 away from being in order.
And then 12345678 * 8 is 98765424 which is +9 away from also being in order.
For binary, it looks like (1-(b-1))/1=b-10 or (1-(2-1))/1=2-2=0 in decimal.
For trinary, it looks like (21-(b-1))/12=b-2 or (7-(3-1))/5=5/5=1 in decimal.
For quaternary, it looks like (321-(b-1))/123=b-2 or (57-(4-1))/27=54/27=2 in decimal.
Essentially and perhaps unsurprisingly, the size of the slices in the number pie get smaller the bigger the pie gets. In binary, the slice is the pie, which is why the division comes out to zero there.
"Why include a script rather than a proof? One reason is that the proof is straight-forward but tedious and the script is compact.
A more general reason that I give computational demonstrations of theorems is that programs are complementary to proofs. Programs and proofs are both subject to bugs, but they’re not likely to have the same bugs. And because programs made details explicit by necessity, a program might fill in gaps that aren’t sufficiently spelled out in a proof."
What I was actually good, or at least fast at, was TI-Basic, which was allowed in a lot of cases (though not all). Usually the problems were set up so you couldn’t find the solution using just the calculator, but if you had a couple of ideas and needed to choose between them you could sometimes cross off the wrong ones with a program.
The script the author gives isn’t a proof itself, unless the proposition is false, in which case a counter example always makes a great proof :p
(Also: complementary != complimentary.)
a) it can be actually helpful to check that some property holds up to one zillion, even though it's not a proof that it holds for all numbers; and
b) if a proof has a bug, a program checking the relevant property up to one zillion is not unlikely to produce a counterexample.
I'm gonna blame autocorrect for that one, but appreciate you catching it. Fixed! :)
There’s a technique for unit testing where you write the code in two languages. If you just used a compiler and were more confident about correspondence, that would miss the point. The point is to be of a different mind and using different tools.
Deleted Comment
I’ve never seen a more succinct explanation of the value of coding up scripts to demonstrate proofs.
I think I’ll tighten it up to “proofs have bugs” in the future.
Dead Comment
0.987654321/0.123456789 = (1.11111111-x)/x = 1.11111111/x - 1 where x = 0.123456789
You can aproxímate 1.11111111 by 10/9 and aproxímate x = 0.123456789 using y = 0.123456789ABCD... = 0.123456789(10)(11)(12)(13)... that is a number in base 10 that is not written correctly and has digits that are greater than 9. I.E. y = sum_i>0 i/10^i
Now you can consider the function f(t) = t + 2 t^2 + 3 t^3 + 4 t^4 + ... = sum_i>0 i*t^i and y is just y=f(0.1).
And also consider an auxiliary function g(t) = t + t^2 + t^3 + t^4 + ... = sum_i>0 1*t^i . A nice property is that g(t)= 1/(1-t) when -1<t<1.
The problem with g is that it lacks the coefficients, but that can be solved taking the derivative. g'(t) = 1 + 2 t + 3 t^2 + 4 t^3 + ... Now the coefficients are shifted but it can be solved multiplying by t. So f(t)=t*g'(t).
So f(t) = t * (1/(1-t))' = t * (1/(1-t)^2) = t/(1-t)^2
and y = f(0.1) = .1/.9^2 = 10/81
then 0.987654321/0.123456789 ~= (10/9-y)/y = 10/(9y)-1 = 9 - 1 = 8
Now add some error bounds using the Taylor method to get the difference between x and y, and also a bound for the difference between 1.11111111 an 10/9. It shoud take like 15 minutes to get all the details right, but I'm too lazy.
(As I said in another comment, all these series have a good convergence for |z|<1, so by standards methods of complex analysis all the series tricks are correct.)
If you multiply term by term every term has coefficient 1 of course. There are n terms with exponent n+1, made from the n sums of the first exponent and the second exponent.
Eg 1+5, 2+4, 3+3, 4+2, 5+1.
So (1/9)^2 = (sum 1/10^i)^2 = 1/10 sum i/10^i
The derivative trick is more useful generally, but this method gets you the solution to 0.12345678.. in an quick way that's also easier to justify that it works.
In general, sum(x^k, k=1…n) = x(1-x^n)/(1-x).
Then sum(kx^(k-1), k=1…n) = d/dx sum(x^k, k=1…n) = d/dx (x(1-x^n))/(1-x) = (nx^(n+1) - (n+1)x^n + 1)/(1-x)^2
With x=b, n=b-1, the numerator as defined in TFA is n = sum(kb^(k-1), k=1…b-1) = ((b-2)b^b + 1)/(1-b)^2 = ((b-2)b^b + 1)/(1-b)^2.
And the denominator is:
d = sum((b-k)b^(k-1), k=1..b-1) = sum(b^k, k=1..b-1) - sum(kb^(k-1), k=1..b-1) = (b-b^b)/(1-b) - n = (b^b - b^2 + b - 1)/(1-b)^2.
Then, n-(b-1) = (b^(b+1) - 2b^b - b^3 + 3b^2 - 3b +2)/(1-b)^2.
And d(b-2) = the same thing.
So n = d(b-2) + b - 1, whence n/d = b-2 + (b-1)/d.
We also see that the dominant term in d will be b^b/(1-b)^2 which grows like b^(b-2), which is why the fractional part of n/d is 1 over that.
I disagree with the author that a script works as well as a proof. Scripts are neither constructive nor exhaustive.
(147 + 369) / 2 = 258
and
(741 + 963) / 2 = 852
(741 + 963)/2 = (700+900)/2 + (40+60)/2 + (1+3)/2, it's just average in each decimal place.
741 + 369 & 963 + 147 | 123 + 987 & 321 + 789 (left right | up down)
159 + 951 & 753 + 357 | 258 + 852 & 456 + 654 (diagonally | center lines)
the design of a keypad... it unintentionally contains these elegant mathematical relationships.
i call this phenomena: outcomes of human creations can be "funny and odd", and everybody understand that eventually there will be always something unpredictable.
For non-Americans and/or those too young to remember when landline service was still dominant, in the 90s and early 2000s AT&T ran a collect-call service accessible through the number 1-800-CALL-ATT (1-800-225-5288) and promoted it with ads featuring comedian Carrot Top. And if you don't know who Carrot Top is, maybe that's for the best.
Deleted Comment
https://math.stackexchange.com/a/2268896
Apparently 1/9^2 is well known to be 0.12345679(012345679)...
EDIT: Yes it's missing the 8 (I wrote it wrong intially): https://math.stackexchange.com/questions/994203/why-do-we-mi...
Interesting how it works out but I don't think it is anywhere close to as intuitive as the parent comment implies. The way its phrased made me feel a bit dumb because I didn't get it right away, but in retrospect I don't think anyone would reasonably get it without context.
Eg 12345679*6*9 = 666666666
1/81 is 0.012345679012345679....
no 8 in sight
Then you have (x + 2 x^2 + 3 x^3 + ...) = (x + x^2 + x^3 + x^4 + ...) + (x^2 + x^3 + x^4 + x^5 + ...) + (x^3 + x^4 + x^5 + x^6 + ...) (count the number of occurrences of each power of x^n on the right-hand side)
and from the sum of a geometric series the RHS is x/(1-x) + x^2/(1-x) + x^3/(1-x) + ..., which itself is a geometric series and works out to x/(1-x)^2. Then put in x = 1/10 to get 10/81.
Now 0.987654... = 1 - 0.012345... = 1 - (1/10) (10/81) = 1 - 1/81 = 80/81.
987,654,321 + 123,456,789 = 1,111,111,110
1,111,111,110 + 123,456,789 = 1,234,567,899 \approx 1,234,567,890
So 987,654,321 + 2 x 123,456,789 \approx 10 x 123,456,789
Thus 987,654,321 / 123,456,789 \approx 8.
If you squint you can see how it would work similarly in other bases. Add the 123... equivalent once to get the base-independent series of 1's, add a second time to get the base-independent 123...0.
For base 2, the ratio is 1/1. When we apply the correction, we get (1 - 1) / (1 + 1) = 0, which is 2 - 2.