shmoe

You've answered something that isn't quite equivalent. (phi(1)+..+phi(N))/(1+...+N) is the probability that a pair selected from A={(n,m)| 1<=m<=n<=N} has gcd(n,m)=1. This isn't the same as selecting from the set B={(n,m)| 1<=m<=N, 1<=n<=N} as I originally asked for. The diffence is the diagonal, the points where n=m. The map f from B to A that orders the pair (e.g. f(1,2)=(2,1)) is a 1-1 map on the diagonal but 2-1 everywhere else (f(1,2)=f(2,1)). Essentially, you're giving the diagonal elements more weight and your probability of relatively prime pair for any N is smaller. Since there are only N elements on the diagonal and N^2 choices overall, this doesn't affect the limit though. About the appearance of the 1/zeta(2) in the solution, this is no accident of course. Using the relation of phi with the mobius function you can prove, for Real part of s>2: [math]\sum_{n=1}^\infty\frac{\phi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}[/math] if you look up Perron's formula you will find an analytic approach to approximating the summatory function of the coefficients of a Dirichlet series like this.

That's essentially it woelen, here's how you can deal with the error terms. I'll use [x] to denote the floor of a real number x. Note that [x] is always within 1 of x, so [x]=x+O(1). This gives [x]^2=x^2+O(x) and [x]=O(x) . [math]\sum_{k\leq N}\phi(k)=\sum_{k\leq N}k\sum_{dm=k}\frac{\mu(d)}{d}[/math] this can is the sum over all d and m where d*m<=N. Changing this to a sum over d and m and using the formula for the sum of the first n integers gives (we can pull the d out of the inner sum): [math]=\sum_{d\leq N}\frac{\mu(d)}{d}\sum_{m\leq [N/d]}md=\sum_{d\leq N}\frac{\mu(d)}{d}d\left(\frac{[N/d]^2}{2}+\frac{[N/d]}{2}\right)[/math] replacing [N/d] with N/d gives: [math]=\frac{N^2}{2}\sum_{d\leq N}\frac{\mu(d)}{d^2}+O\left(\ \sum_{d\leq N}\frac{N}{d}\right)=\frac{N^2}{2}\sum_{d\leq N}\frac{\mu(d)}{d^2}+O\left(N\log{N}\right)[/math] since [math]\sum_{d\leq N}d^{-1}=O(\log{N})[/math], just bound the sum by the corresponding integral. Also bounding by an integral, you can show [math]\sum_{d> N}\mu(d)d^{-2}=O(N^{-1})[/math], which gives [math]\sum_{d\leq N}\mu(d)d^{-2}=\zeta(2)^{-1}+O(N^{-1})[/math]. Inserting this into the above and we get: [math]\sum_{k\leq N}\phi(k)=\frac{N^2}{2\zeta(2)}+O\left(N+N\log{N}\right)=\frac{N^2}{2\zeta(2)}+O\left(N\log{N}\right)=\frac{3}{\pi^2}N^2+O(N\log{N})[/math] which proves your limit. Now, if P(N) is the probability that two randomly selected integers less than or equal to N are relatively prime, what is the limit of P(N) as N-> infinity? You can likewise show that [math]\sum_{k\leq N}\frac{\phi(k)}{k}=\frac{6}{\pi^2}N+O(N\log{N})[/math] using the same approach (this will be slightly simpler), or you can use partial summation to get from one result to the other (partial summation is the 'integration by parts' of summation, it's actually integration by parts for Riemann-Stieltjes integrals). This leads to the conclusion that the 'average value' of phi(n)/n is 6/pi^2.

You are using O(n) in a non-standard way, at least not one I'm familiar with if you think saying phi(n) is on average of order O(n) is anything but a trivial statement. I guess you mean to say phi(n) is "close" to n for "lots" of values of n? This, or a precise statement of this, is essentially equivalent to proving you limit is something non zero. We can find the 'average' value for phi(n)/n (average in an asymptotic kind of sense). I'll give some details once you've resolved your limit. I'm telling you it is the latter case! Everything you need is in my last post. I can fill out the details if you like, but I'll wait until you ask for them.

Ahh, so you don't have the answer. I had thought you did for the same reason matt did, when you said "This limit is defined and has a very nice and surprising value". You can compute values as high as you like, it does not show this limit exists! And no, I wouldn't consider some as yet to be identified randomish looking string of digits 'nice' in any way. From your last post...phi(n) is O(n), you trivially have phi(n)<n. To do this problem, use [math]\phi(n)=n\sum_{d|n}\frac{\mu(d)}{d}[/math] where mu(n) is the mobius function (the sum is over divisors d of n). Change order of summation. You'll also need to know that [math]1/\zeta(s)=\sum_{n=1}^{\infty}\mu(n)n^{-s}[/math] when the real part of s>1. The limit is indeed a 'nice' value as matt was guessing at (expressible in terms of naturally occuring well known constants), and it's not unrelated to the question he posed earlier (another reason I thought you might have known the answer!) I don't have the proof about the taylor polynomials of e^x, but you should be able to find it with his name and the year given. Did you try mathscinet?

Why would you bother with the computation? At any rate, if my memory of error terms serves*, S(N)/N^2 should be within 1/N of the actual limit (the error is O(1/N), I think 1 worked as a constant, but I'm not positive). *edit-my memory of error terms failed me, O(log(N)/N) is easy enough to prove, I had thought the log could be removed with more work. It can be reduced a little bit, but apparently not to something less than logloglog(N), so a constant is right out. see http://www.mai.liu.se/~halun/complex/taylor/

Consider what adding the digits together does to your number mod 9. (For your pattern, it should be mentioned that you repeat this 'adding the digits together' operation until you get a single digit)

This isn't what x^x^x... represents. It's the limit of the sequence x^x, x^(x^x), x^(x^(x^x)),... what you are doing on your calculator appears to be x^x, (x^x)^(x^x), ((x^x)^(x^x))^((x^x)^(x^x)),... which is something different. With x=sqrt(2) you'll get: x=1.414213562.... x^x=1.632526919... x^(x^x)=1.760839556... You can keep going, it will be approaching 2 but of course doing a finite number of terms proves nothing at all. You should prove (when x=sqrt(2)) that a) this sequence is increasing b) this sequence is bounded above by 2 (induction for both). This will prove the limit does in fact exist, you can then do some manipulations (combined with continuity of the exponential) to show this limit is 2.

Do you mean: [MATH]\lim_{n\rightarrow \infty}\frac{n}{\sqrt{\sum_{k=1}^{n} k^2}}[/MATH] As you had it doesn't make much sense. It's not the case that [MATH]\sum_{k=1}^{n} k^2[/MATH] is equal to [MATH]\int_{1}^{n} t^2 dt[/MATH] either' date=' but you can use integrals to bound the sum: [MATH']\int_{0}^{n} t^2 dt\leq\sum_{k=1}^{n} k^2\leq\int_{1}^{n+1} t^2 dt[/MATH] Note the endpoints carefully (draw a graph of these). Your (n^3-1)/3 will be a lower bound also, good enough for this problem (maybe you just meant to bound it, but you had said "rewrite", which was troubling). See http://mathworld.wolfram.com/PowerSum.html for more on power sums, equation (23) and (33) are the relevant ones here.

No, you can't skip out on the definitions. If you do you will literally have no idea what you are talking about- the symbols have no inherent meaning, only the meaning mathematicians assign to them. In my experience, the majority of the people who have problems with 0.99...=1 won't even be able to tell you what the symbol "0.99..." means and yet they feel qualified to make statements about it. This gets annoying fast to anyone who has actually taken the time to understand what the real numbers are (something you don't do in high school, or even your typical intro calculus class), and is why you'll see short replies suggesting they should go and do some much needed reading. If they aren't willing to dive into the details, they will never be qualified to have an opinion worth more than dirt. You linked to a source for a woefully inadequate definition of the real numbers. I would suggest you avoid using what appears to be a glossary on a philosophy website for mathematical definitions. If you want to learn about the reals, go crack opens some textbooks. Any intro to real analysis book will probably do (or something like Spivak's Calculus), look for something that gives a construction of the reals from the more familiar rationals (though theres probably plenty of stuff online). This is admitedly lazy on my part, but it's a much better use of my time if you go away, read, and come back with questions than me building up a detailed theory from scratch when it already exists in many places.

Anything beyond intro calculus texts and "ln" has largely vanished, though even in these texts it's not a given that you'll see "ln".

Absolutely. This sort of reduction is a good lead in to uses of Fermat/Euler though. Alas, they probably weren't capable of dividing polynomials either. I honestly don't know what they make them do in high school anymore. When I first learned about the Euclidean algorithm to write the gcd as a linear combination I remember thinking how bloody cool division was and wondering why this wasn't taught in grade school. It's such a simple idea, yet so very clever.

In addition to not being able to do the arithmetic, they don't like equivalence relations. This is also suprising since they've been implicitly using equivalence relations on the rational numbers since I don't know how early. @the tree- If you've just been introduced to modular arithemtic then I would suggest doing everything by hand until it's mind numbingly easy. It is grade school stuff like matt has said, so this shouldn't take long to come back. 2^31+1 mod 7... you'll learn Fermat's Little Theorem (and Euler's) later and it will be perhaps more obvious. That's overkill for numbers this small though. What is 2^3 mod 7 and how does this help find 2^31?

Now you know better. Go to the library and browse through some advanced math texts and see for yourself (anything beyond elementary calculus). If you like, you can write the authors and let them know your calculator says their notation is wrong. Bring alot of stamps though, you'll need them.

It should not be necessary. However, if you are doing many calculations involving large numbers than mechanical means can be handy to save time. I would say if the division algorithm isn't an utterly trivial thing then it should be done by hand until it is before turning to a calculator for help. In retrospect though I do regret posting a way of doing it with a calculator. I should have demanded the tree come up with one on his own- it's really not difficult with even a basic understanding of mod. I was feeling lazy I suppose.

Only if you are unfortunate enough to be trapped in a first year calculus class. "log" denotes the natural logarithm in higher maths. Sometimes it will mean "base-2" if you're trapped in a computer science class (sometimes "lg" is used here). Universal meaning in higher maths: "log" without an explicitly mentioned base means "whatever base makes this statement true" if it matters and "whatever the readers favorite base is" if it doesn't.

Cross product: http://planetmath.org/encyclopedia/CrossProduct.html If your triangle has vertices given by the vectors u,v,and w, then take a=v-u and b=w-u (not the only choices), these will be vectors in the directions of two of the sides. axb and bxa will both give normals, but in opposite directions, axb=-(bxa)

I don't think I've ever seen a calculator with a built in mod button. I assume you're interested in finding the least non-negative integer congruent to x mod n say. If you want to find x mod n you can first take the floor(x/n) (just drop the digits decimal of x/n). Then find x-n*floor(x/n). e.g. 34 mod 5, your calculator gives 34/5=6.8. Floor(6.8)=6. 34-5*6=4 You can also do n*frac(x/n), where frac is the decimal part. e.g. frac(6.8)=.8, but depending on how your calculator stores the decimal this could cause problems from rounding errors.

aardvark, kiss, ball, hoop, canning, cattle, etc... or did you mean something else?

I read Gleick when I was in high school. At the time I thought it was great. In retrospect "handwavy load of crap about nothing" is more accurate though possibly a tad harsh. The danger is that you may walk away from the book with the impression of 'chaos' that annoys the heck out of matt. These kinds of math-free popsci books are mostly good for the tidbits of folklore inside, you won't learn much (or any) actual math from them. Two books I really enjoyed in high school were by Paulos, "Innumeracy" and "a mathematician reads the newspaper". You probably won't learn any math from them either, but they are pretty amusing and I think good books for the 'average' person to read. Derbyshire's "Prime Obsession" is a decent treatment of the Riemann Hypothesis (for the laymen). It has some great history in it and I think the math content should be at a good level for a high school student (hard to tell) though it necessarily has plenty of handwaving. Hardy's Apology is sad but enlightening. No math here, but a good read. Get a later edition with the lengthy foreward by Snow. I haven't seen the book by Korner before, it looks interesting.

it's 8, what the second poster was refering to. It can be represented as (1)(2, 3, 5, 9, 17, 33, 14, 27)(4, 7, 13, 25, 49, 46, 40, 28)(6, 11, 21, 41, 30, 8, 15, 29)(10, 19, 37, 22, 43, 34, 16, 31)(12, 23, 45, 38, 24, 47, 42, 32)(18, 35)(20, 39, 26, 51, 50, 48, 44, 36)(52) where 1 is the bottom card. As you say, a perfect shuffle is possible with practice and a good deck. Getting 8 in a row takes *much* talent (or a heap of luck) but is still possible. I wonder what this turns out to be. Crude upper bound is 52! like you said, but we can improve this without much work. Any permutation can be written as a product of disjoint cycles. In this form it's order is the lcm of the length of these cycles. Thus any s in S_52 has order dividing lcm(52,51,50,...1)=2^5*3^3*5^2*7^2*11*13*...*47=3099044504245996706400 On second thought, this appears to give lcm(ord(s)), since we can easily demonstrate a shuffe of each admissible prime ower order. There's no lone element of this giant order though. I would think it's not too difficult to come up with the highest order element, just consider its decomposition into disjoint cycles, they'd have to be prime powers and the sum would have to be less than 52, so not too many options a computer could search quickly.

On the contrary, it's extremely important for a mathematician. You won't find a mathematician trying to prove results about hand wavy or vague definitions and there are plenty of "the probability a random integer is blah" statements, for example, The probability a random integer is divisible by 3 is 1/3. The probability a random natural number is prime is 0. The probability two randomly selected natural numbers are coprime is 6/pi^2. In these cases "Probability of a randomly selected blah" is in the sense of asymptotic density that can be made precise. What's often overlooked by the casual observer is that there is no way to select a random integer uniformly from the entire set of integers. Since a uniform distro. is what we're after, we end up using uniform distribution on finite sets and taking limits, etc.

Do you need to explicitly exhibit a bijection or is it enough to prove one exists?

This doesn't follow without more work: [hide]Namely the product of the 11 smallest numbers in a set isn't necessarily less than the product of the rest of the numbers. Since you have 89>=11 other numbers, it will be sufficient to show that these are all greater than 1 (it would also be enough to show the 78 largest are >=1). This follows since at least one of the smallest 11 must be greater than 1, else we couldn't have A>1[/hide]