finrodffelagund: (magicspecial)
[personal profile] finrodffelagund

This is something that I thought of while I was in college, some thirty years ago, and I never thought of posting it until now.

First, definitions: the natural numbers are simply the numbers 1, 2, 3, etc., the positive whole numbers. I came up with a function f(n) defined over the natural numbers as follows:

f(1) = 1.

f(n) for n being a natural number is as follows: list out all the factors of n that aren't n itself, call them k1, k2, .. kp. Then f(n) = f(k1) + f(k2) + f(k3) + ... + f(kp).

Examples:

Factors of 2: 1.
f(2) = f(1) = 1.
Factors of 3: 1.
f(3) = f(1) = 1.
Factors of 4: 1, 2.
f(4) = f(1) + f(2) = 1 + 1 = 2.
Factors of 5: 1.
f(5) = f(1) = 1.
Factors of 6: 1, 2, 3.
f(6) = f(1) + f(2) + f(3) = 1 + 1 + 1 = 3.
Factors of 7: 1.
f(7) = f(1) = 1.
Factors of 8: 1, 2, 4.
f(8) = f(1) + f(2) + f(4) = 1 + 1 + 2 = 4.
Factors of 9: 1, 3.
f(9) = f(1) + f(3) = 1 + 1 = 2.
Factors of 10: 1, 2, 5.
f(10) = f(1) + f(2) + f(5) = 1 + 1 + 1 = 3.
Factors of 11: 1.
f(11) = f(1) = 1.
Factors of 12: 1, 2, 3, 4, 6.
f(12) = f(1) + f(2) + f(3) + f(4) + f(6) = 1 + 1 + 1 + 2 + 3 = 8.

What can we prove about this function? Let's start off easy.

A prime number is a natural number where its only factors are 1 and itself, therefore for all prime numbers p, f(p) = f(1) = 1.

What about p^2? Its factors are 1 and p, so f(p^2) = f(1) + f(p) = 1 + 1 = 2. Similarly, for p^3, f(p^3) = f(1) + f(p) + f(p^2) = 1 + 1 + 2 = 4. f(p^4) = f(1) + f(p) + f(p^2) + f(p^3) = 1 + 1 + 2 + 4 = 8.

How about for p*q, where p and q are both prime and p <> q? Its factors are 1, p, and q, so f(p*q) = f(1) + f(p) + f(q) = 1 + 1 + 1 = 3, for all numbers that are the product of two different primes.

Now for something a bit more gnarly. I assert that for all primes p and all natural numbers n, that f(p^n) = 2^(n-1). We can prove this via a mathematical principle called induction, where if you want to prove something is true for all natural numbers, you need only do two things: first, prove it's true for 1; second, assume it's true for natural number n and use that to prove it's true for n+1. The first is easy: f(p^1) = f(p) = 1 and 2^(1-1) = 2^0 = 1. Now let's assume that my statement is true for n. What is f(p^(n+1))? f(p^(n+1)) = f(1) + f(p^1) + f(p^2) + ... + f(p^(n-1)) + f(p^n) because its factors are 1, p, p^2, ..., p^(n-1), p^n. Similarly, the factors of p^n are 1, p, p^2, ..., p^(n-1), so f(p^n) = f(1) + f(p) + f(p^2) + ... + f(p^(n-1)). Use the latter equation to substitute in the former and you get f(p^(n+1)) = f(p^n) + f(p^n). Since we're assuming that my statement is true for n, then f(p^n) = 2^(n-1). Therefore f(p^(n+1)) = 2^(n-1) + 2^(n-1) = 2^n = 2^((n+1)-1), which is what we were trying to prove.

If you didn't get that, that's ok, after all I did say it was a bit more gnarly. If you did, then ponder this.

Suppose you have two natural numbers c and d, and you write out their prime factorizations, and they look like this, where p1, p2, ..., pk are distinct primes and q1, q2, ..., qk are another set of distinct primes of the same size, but the ps and qs aren't necessarily distinct from each other, and n1, n2, ..., nk are any set of natural numbers:

c=p1^n1 * p2^n2 * ... * pk^nk
d=q1^n1 * q2^n2 * ... * qk^nk

(Two numbers where the exponents in their prime factorizations are the same, but the primes might be different but don't have to be.)

My hypothesis is that f(c) = f(d) in all such cases.

The previous proofs prove this for the special cases where k=1, and for k=2 and n1=1 and n2=1.

I explained my hypothesis to the math department at my college; one professor said "Well, that's obvious", and another professor said "I don't see that at all". I never did get around to proving it, because to really prove it easily I needed some kind of multi-dimensional recursion, and while someone has doubtless established such a thing, I didn't know about it then and didn't want to try establishing it myself.

So, to those of you that made it this far: is it obvious, or do you not see it at all? Or, do you know of someone that's worked out and shown the principles of n-dimensional recursion which would make proving something like this very easy?

Profile

finrodffelagund: (Default)
FinrodFFelagund

March 2017

S M T W T F S
   1234
567891011
12131415161718
19202122232425
262728293031 

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 26th, 2017 10:45 am
Powered by Dreamwidth Studios