It's a fact

[sniffnoy]

We have qualified for NAQT nationals, and in Division 1 our A and B teams did. Bruce kind of forgot about our C team's existence and sent out an email saying everyone qualified.

"You know nothing about my baby-cow-jumpingness-skills!" -Sayer

This came up when we were trying to think of words other than "fnord" containing "fn". Someone pointed out we can take adjectives ending in 'f' and add "-ness"; this got us "buffness" and "stiffness". Unfortunately "tough" and similar words end in "gh" rather than "f".

I cannot find any way through the 7th dungeon. Michael Toney told me how to get past the "Grumble, grumble..." guy, but I still can't find any way through. I've tried bombing every wall that might lead somewhere. I've tried pushing on pretty much every block (quite possibly actually every block) and I've tried using the whistle in every room. There's obviously something I'm missing here.

So! The math problem I said I would write about. A few days ago something caused me to recall the a^4=a problem. Now, an important step in the solution of that, and also the much easier a^2=a problem, is showing that your ring is of characteristic 2. If you have a^3=a, though, the most you can say is that it's of characteristic 6 (I'm just going to say "characteristic n" rather than "characteristic dividing n"), because Z₆ satisfies a^3=a. So the question is then, what is this in general? I.e., what's the least bound (under the divisibility order) you can get on the characteristic if a^n=a? With a bit of thought it's obvious that this has to be gcd{k^n-k:k∈Z} (and this a max as well). So I wrote up a program to calculate this - Lucas was pretty confused when I told him this, saying, How do you write a program to calculate a GCD over *all* the integers?; it's not that hard, you ought to be able to see how. Originally I tried to write one that actually worked quickly, but it didn't work at all - I think the general algorithm was probably right, but I was feeling impatient, so rather than try to debug it I just wrote a simpler one that ran in exponential time. It was still good enough for calculating it out to 21 terms, which was more than necessary. Anyway, I got this:

n     0 1 2 3 4  5 6  7 8  9 10 11 12   13 14 15 16  17 18  19 20  21
f(n)  1 0 2 6 2 30 2 42 2 30  2 66  2 2730  2  6  2 510  2 798  2 330

OK, so, ignoring the initial 1,0, which are special cases, what do we notice? Obviously the even terms are always 2... but those odd terms look familiar, too. They're the denominators of the Bernoulli numbers! I check on Sloane for information. Sure enough, with the initial 1,0 removed, the sequence comes up: A027760. They have it on a different offset - in the comments, it says it's the gcd{k^(n+1)-k:k∈Z} but what the sequence is actually listed as is the denominator of sum{1/p:p-1|n} (or they could just say product{p:p-1|n}), or, under my offset, f(n)=product{p:p-1|n-1}. Oh right, Clausen-von Staudt theorem! I'd forgotten about that! So indeed it would be the denominator of the n-1th Bernoulli number for odd n, and 2 for even n. (Note that this does not apply for n=0 or 1, though it works for 1 if you replace "product" with "lcm", seeing as they are relatively prime...) Now the problem is proving that. Let's define g(n)=product{p:p-1|n-1}. It's pretty easy to see that g(n)|f(n), and Lucas points out that in fact the prime factors of g(n) can be the only prime factors of f(n) as well. So the problem then is showing that f(n) is squarefree. I've figured this out for the case where n even - so I've proven that those are all 2 - but I have no idea what to do if n odd. We have that if p^k|f(n), then φ(p^k)|n-1 (note that the reverse is only true if k=1), which is how I did the n even case, but so far it hasn't really helped if n odd. And that's where that stands.

-Sniffnoy

Comments

[fensef.livejournal.com]

Nice! I'm going to try working on the a^4=a problem (yes, I did the a^2=a problem in Herstein) now that I might be able to get it (and no longer remember Tom's sol'n).

Neil Sloane is coming to Rutgers to talk this Thursday, but I have an exam during his talk! Dang phtooey.

-Avi

[sniffnoy.livejournal.com]

Try the a^3=a problem too; I've solved it now, as you'll see if you read further (you'll also see that I proved why that gcd is, in general, squarefree; it's pretty easy, actually, so I didn't give the solution here. Do that yourself. :) Of course, you don't need that just do the n=3,4 cases, but...) The solutions are quite similar, and if you can get one the other shouldn't be too hard. I'm currently trying to see if I can get it for any other n... those look to be considerably harder (if it's even true).

[unended01.livejournal.com]

I can tell you how to get past the "Grumble, grumble..." guy. (Sorry, I found this entry through a google search, but I know the answer, so if you still don't know...)

[sniffnoy.livejournal.com]

Reread that. "Michael Toney told me how to get past the 'Grumble, grumble...' guy, but I still can't find any way through." I already knew. And I beat that quite a while ago.

[unended01.livejournal.com]

Well done! (I was just checking...)