Let f(n) be a function from the natural numbers from the natural numbers. Suppose further that f(1)=1, and assume that f(n) is equal to the number of positive integers k that are less than equal to n and satisfy f(k) | k. Then it is not hard to show that in fact f(n)=n. Now suppose we instead look at the exact same thing, but insist that f(n) count the number of k that are at most n and satisfy f(k)|P(k) where P is some fixed polynomial with integer coefficients.
For some choices of P, we do not have any function f which would satisfy the desired recursion. For example, if P(x)=x+1 we don't have any function f satisfying the recursion. To see this, note that we have either f(2)=1 or f(2)=2. If f(2)=1, then f(1)|1, and f(2)|2, so in fact f(2)=2. Consider the other case where f(2)=2. If so, since 2 does not divide 3, we must have f(2)=1. Contradiction and nd of p.
Here's my question which I have not been able to make substantial progress on: Are there any valid choices of P and f that satisfy the recursion and don't have f(n)=n for all n?
Subscribe to:
Post Comments (Atom)
8 comments:
There is a typo in the post. You mean to say that f(n)= n in the first paragraph.
OK, I've got one. Let P(n)=n+2. Then f(n)=⌊n/2⌋+1 is a consistent solution.
Proof: f(1)=1 matches up, so what we need is that it is consistent for f to increase on even numbers and fail to increase on odd numbers greater than 1, i.e., that for n even, n/2+1 | n+2, and for n odd and greater than 1, (n+1)/2 does not divide n+2. The former is obvious, and the latter is true unless n|2, i.e., it's true for n>1.
Now I suppose the question is, can we find an example where the solution is non-unique? (I haven't checked uniqueness for this case, though f(n)=n certainly doesn't work!)
Johan, thanks for that corrected.
Harry, yeah, that example checks out. I haven't thought about uniqueness really.
So where did this problem come from, anyway?
A very wandering mind.
For reasons that aren't clear to me, I was thinking about for a given well-behaved function f, counting n less than x satisfying f(n)|n. Call this function f*. I then was thinking about iterating the * operation. Naively, one expects the * operation to alternate between functions that climb quickly and functions that climb slowly. So then I was thinking about fixed points of *, which leads to this fairly naturally.
And the introduction of a polynomial was just the natural next step, obviously. :P
Actually at first I missed where you said integer coefficients, and was wondering if you meant integer coefficients or just integer-valued; but an example with integer coefficients exists, so yay.
Now I am going to go not think about the uniqueness problem...
Actually, managed to find an example for that as well: Take P(n)=n(n+2). Then both f(n)=n and f(n)=⌊n/2⌋+1 work.
Post a Comment