= 27d567bc2d48d9f40e9ccc20ea370b15)
MrHen comments on Bizarre Illusions - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (305)
I think you're really failing to grasp the content of the unique factorization theorem here. Firstly we don't think about factored numbers as products of primes up to permutation, we think of them as products of distinct prime powers (up to permutation, I suppose - but it's probably better here to just take a commutative viewpoint and not regard "up to permutation" as worth specifying). But more importantly, you need to take a multiary view of multiplication here, not a binary one. 1 is the empty product, so in particular, it is the product of no primes, or the product of each prime to the 0th power. That is its unique prime factorization. To take 1 as a prime would be like having bases for vector spaces include 0. Almost exactly like it - if we take the Z-module of positive rationals under multiplication, the set of primes forms a free basis; 1 is the zero element.
For some reason, I never imagined factors this way.
18 = 3^2 * 2^1
97,020 = 2^2 * 3^2 * 5 * 7^2 * 11
I suppose I have seen them printed out that way, but the deeper structure there never clicked. Cool.
As it happens I'm partway through "An Introduction to the Theory of Numbers" by Niven, Zuckerman, and Montgomery at the moment. Lots of problems are incredibly easy to solve given this structure. The example that springs to mind is the very straightforward proof why the combinatorial formula n! / (r! (n-r)!) always gives you an integer.
Update: Well having been scored up I feel like I should give a hint on the actual proof: for any prime p and any n, the greatest power of p that divides n is
\sigma_{i=1}^{\infty} floor( \over{n}{p^i} )
and for any real numbers a, b, floor(a + b) >= floor(a) + floor(b).
Oh for real TeX markup!
Do you recommend the book? If I were interested in the subject, is this good to pick up or can you think of a better option?
I'm enjoying it, but it touches on abstract algebra as an alternative approach rather than leaning on it for everything; I'd kind of prefer the latter.
You may be a good person to ask this question:
I was wondering if there was a function f(x, y, z) so that x and z represent the left and right sides of common mathematic operators and y represents the level of operation. So f(1, 2, 4) would be 1 + 4 and f(2, 2, 4) would be 2 * 4. Better versions of f(x, y, z) would have fewer end cases hardcoded into it.
The reason behind this is to handle operator levels greater than addition, multiplication, and exponents. The casual analysis from my grade school and undergrad level math shows the pattern that multiplication is repeated addition and exponents are repeated multiplication.
My quick attempts at coming up with such a function are spiraling into greater and greater complexities. I figured someone else has to have thought about this. Do you know of a place I can start reading up on ideas similar to this? Is what I am doing even plausible?
Quick thoughts based on me playing around:
Ackermann function
Knuth's arrow notation
Cool, thanks. It seems like one of my first tries was producing numbers similar to the Ackermann function. Knuth's arrow notation essentially takes over after multiplication. But those two articles will give me enough to read to keep moving on. :)
Do you know of any that go the other way into smaller and smaller numbers?
EDIT: I found the right subject name through links on your links. It is called hyperoperation.
1 / Ackermann function.
Sure, that works, but it isn't exactly what I am looking for. Is it possible to express the division operator in a manner similar to how multiplication can be expressed using addition? My instinct is telling me probably not.
Hyper operators. You can represent even bigger numbers with Conway chained arrow notation. Eliezer's 3^^^^3 is a form of hyper operator notation, where ^ is exponentiation, ^^ is tetration, ^^^ is pentation, etc.
If you've ever looked into really big numbers, you'll find info about Ackermann's function, which is trivially convertable to hyper notation. There's also Busy Beaver numbers, which grow faster than any computable function.
Yes, this is exactly what I was looking for. Thank you.