Question

My friend gave me this problem

Answer 1

let \[n=\prod_{i=1}^\infty p_i^{a_i}\] and \[f(n) = \prod_{i=1}^\infty a_i p_i^{a_i-1}\]

prove that there are infinitely many solutions to:

\[f(n)=f(n-1)+1\]

Answer 2

I don't like ur friend atm lol

Answer 3

I honestly don't even know if this is true, I believe he got it out of like one of the problem sets he usually gets his problems out of but he had to leave so who knows lol.

Answer 4

Never seen a problem like this

Answer 5

This question is a bit confusing gaah XD Kainui smh you friend is gr8 m8y XD

Answer 6

can we just say that since there are infinitely many primes, depending on where you stop you will always get a distinct answer by the FTA

Answer 7

Can you believe there 11 people looking at this

Answer 8

11 of us are looking at this and none of us a helping XD XD XD XD CLASSIC XD

Answer 9

11? that's nothing I've seen way more

Answer 10

and no one knows?

Answer 11

Wow

Answer 12

\(\color{blue}{\text{Originally Posted by}}\) @FibonacciChick666
can we just say that since there are infinitely many primes, depending on where you stop you will always get a distinct answer by the FTA
\(\color{blue}{\text{End of Quote}}\)

Yeah f(n) is distinct for each n, but that specific arrangement \(f(n)=f(n-1)+1\) though?

Answer 13

Wait i was looking at the problem and started reading and only got to the first letter :/

Answer 14

This assumes that no multiplication of consecutive primes yields one more than the previous multiplication. Right? Like if we were to put this into english versus math, that is the end result?

Answer 15

Empty >.>

Answer 16

are there any restrictions on the \(a_i\)?

Answer 17

Nah, this is just a cute way of writing the prime factorization of n so that I could define what \(f(n)\) does.

Answer 18

Like for instance \(f(25) \ne f(24)+1\) because \(f(25) = 2*5^1\) and \(f(24) = 3*2^2*1*3^0\) so plugged in:

\[10 \ne 12 + 1\]

Answer 19

I have never googled something I have no idea what is so hard in my life.

Answer 20

Haha ok I can try to explain any questions you have about the notation or ideas or anything. It's not so bad, it just looks scary. :P

Answer 21

If that's math then I've just lost my desire to live.

Answer 22

Haha nah, it's good for you. Like this big capital Pi, \(\Pi\) means product. So a completely different example of how to use it is like this:


\[\prod_{n=3}^7 n^2\]

Read it from the bottom there, take the product from n=3 to n=7 of this function \(n^2\). So we do that:

\[\prod_{n=3}^7 n^2 = 3^2*4^2*5^2*6^2*7^2\]

Not toooooo bad I hope?

Answer 23

hm, I guess I misunderstood the notation. So we are saying that for every composite number, The prime factorization of one less than that number plus 1 will always produce a unique result?

Answer 24

Oh, no the question is saying there are infinitely many values of n such that

\[f(n)=f(n-1)+1\] is true

Answer 25

right, but with the function, I am trying to turn this into a question written in english so that it makes more sense. Since f(n) is the product of primes, it appears that we could say they are asking if there are any such cases where you get the product of primes plus 1 for the next number

Answer 26

True, I like that perspective of inverting it, then we could call the f(n) the numbers and reverse it. The main problem is the fact that they're consecutive like this it's what's messing it up, I haven't even found 1 case where it's true lol go figure.

Answer 27

I'm having difficulty understanding how you plugged in 25 above for n. Prime factorization of 25 is so thats 2^0*3^0*4^0*5^2 then f(24)=2^3*3^1* 4^0*5^0
so f(25)=f(24)+1 is the same as the counting principle. You will always get a distinct result when you add 1 to an integer. So, I'm confused as to what the product above means.

Answer 28

I think f(0)=0
\[f(n)-f(n-1)=1 \\ \sum_{n=1}^k (f(n)-f(n-1))=\sum_{n=1}^k 1 \\ -f(0)+f(k)=k(1) \\ -f(0)+f(k)=k \\ 0+f(k)=k \\ f(k)=k\]
Sol we can reduce the problem to solving
f(n)=n

Answer 29

Thats brilliant! So all n's of below form work is it ?
\[n = \prod {p_i}^p\]

Answer 30

so maybe we want to solve
\[a_1 p_1^{a_1-1}=p_1^{a_1} \\\ \\ a_1 p_1^{a_1}=p_1^{a_1+1} \\ a_1=p_1\]

Answer 31

so do these numbers work?

\[n=2^2 \\ n=2^2 \cdot 3^3 \]

Answer 32

just for examples

Answer 33

\[n=2^2 \\ n=2^2 \\ f(n)=2 \cdot 2^{2-1}=2^2=4 \\ f(n-1)=f(3)=3^0 \\ f(n)=f(n-1)+1 \\ 4=1+1 \\ 4=2\]
maybe I made a mistake
I thought the ai=pi

Answer 34

Oh f(n) = n and f(n-1) = n-1 both must satisfy

Answer 35

how did you get that conclusion
just playing around?

Answer 36

from ur recent reply

Answer 37

lol i think you understood my reply better than me
I think I see that now

Answer 38

\[n=2^2 \\ n=2^2 \\ f(n)=2 \cdot 2^{2-1}=2^2=4 \\ \color{red}{f(n-1)=f(3)=3^0 \ne n-1}\\ f(n)=f(n-1)+1 \\ 4=1+1 \\ 4=2\]

Answer 39

that makes sense

Answer 40

f(n)=n for all n

Answer 41

so we also have to have f(n-1)=n-1 for all n

Answer 42

we we need to find two consecutive numbers n-1 and n
such that
\[n-1=p_1^{p_1} \cdot p_2 ^{p_2} \cdots p_k^{p_k} \cdots \\ \text{ and } \\ n=p_1^{p_1} \cdot p_2^{p_2} \cdots p_k^{p_k} \cdots +1 =p_1^{p_1} \cdot p_2^{p_2} \cdots p_k^{p_k} \cdots p_l^{p_l} \dots \]
trying to find one example...

Answer 43

maybe I'm wrong to assume that a_i=p_i....
maybe I should say
\[a_1 \cdot a_2 \cdots a_n=p_1 \cdot p_2 \cdots p_n\]

Answer 44

Here are few solutions
```
13013
26702
49517
63206
67769
81458
```

Answer 45

Wow!!! Brilliant @freckles and @ganeshie8 !

I should have shared some things I had found earlier, they might help, not sure though.

Since \[f \left(\prod_{i=1}^\infty p_i^{a_i} \right) =\prod_{i=1}^\infty f \left( p_i^{a_i} \right) \] this means it's a multiplicative function and since:

\[\gcd(n, n-1)=1\] we also have:

\[f(n)*f(n-1)=f(n^2-n)\]
and just cause 1 pops up, we can also write \(1=f(1)\). So idk if these sorts of things are useful to us or not. Maybe though,

\[f(n)-f(n-1)=f(1)\]
square it?
\[f^2(n)-2f(n^2-n)+f^2(n-1)=f(1)\]

Answer 46

Nah, he solved the equation\[f(n+1) = f(n) + 1\]So just add one to all of those numbers and you'll have your solutions.

Answer 47

Ah ok I see it works now cool :D

Answer 48

err weird I thought had double posted but somehow it flipped and I deleted my original post bleh. Oh well I think I might have just figured out how to solve this now!

Answer 49

Suppose you have a solution:

\[f(n)=f(n-1)+1\]

there are infinitely many primes p, such that \(\gcd(p,n)=\gcd(p,n-1)=1\)

So we can replace:
\[f(n)=f(pn)\] and\[f(n-1)=f(p(n-1))\] to get:

\[f(pn)=f(pn-p)-1\]

Grrr... that's so close but not what we need damn.

Answer 50

I guess it's clear to me now that \(f(a)=1\) when a is square free. Hmmm... maybe that 1 at the end there can be replaced with a squarefree number in the function, like:

\[f(n)=f(n-1)+f(a)\]

Doubt this is useful to us though.

Answer 51

At the very least it seems to generalize freckles solutions a little further, when a and b are square free:

\[f(an)=n\]\[f(b(n-1))=n-1\]

Answer 52

Here is a small result :
\(n = 3888 + 4563k\) is a solution to the given equation whenever \(\dfrac{n}{27}\) is squarefree.

So I guess it is sufficient to prove that there are infinitely many squarefree integers of form \(\dfrac{n}{27}\)

Answer 53

before I try to plug this in and figure it out why this result works, the n you're using is for \(f(n+1)-f(n)=1\) or for \(f(n)-f(n-1)=1\)?

Answer 54

ahh this one \(f(n)-f(n-1)=1 \)

Answer 55

One sec, im gonna change it slightly..

Answer 56

ok, how'd you manage to figure that out, I'm looking at its prime factorization and plugging it in but I can't really see how to use this \(n / 3^3\) is squarefree trick here's my attempt:

\[f(2^43^5+3^313^2k) = f(2^43^2+13^2k)\]

I guess just tell me your strategy for how you're thinking about this

Answer 57

Whoops I think I wrote that backwards, w/e you're about to change it anyways

Answer 58

Here is a small result :
\(n = 3888 + 4563k\) is a solution to the given equation whenever \(\dfrac{n}{27}\) and \(\dfrac{n-1}{169}\) are square free.

Answer 59

I'll explain my method shortly... still playing with it on paper at the moment

Answer 60

It hinges on below observation :
\[3*3^2 = 2*13+1 \]

Answer 61

Ok, I sorta see what you're playing with I like it, I also just found a side distraction of my own so I'll be sorta working on this alternate path and see where it leads so don't feel too rushed

Answer 62

So if we choose \(n\) as \(3^3p_1p_2p_3\ldots \), then \(f(n)\) will be simply \(3*3^2=27\)

Answer 63

We choose \(f(n-1)\) as \(13^2q_1q_2q_3\ldots\), then \(f(n-1)\) will be simply \(2*13=26\)

Answer 64

it remains to solve the equation \(3^3x = 13^2y+1\) over positive integers such that \(x\) and \(y\) are squarefree

Answer 65

\(3^3x = 13^2y+1\) is a linear diophantine equation which can be solved easily

Answer 66

Since \((3^3, 13^2) = 1\), above equation has infinitely many solutions over integers.

But the trick part is, this doesn't prove yet there will be infinitely many "square free" integer solutions

Answer 67

Oh I don't really know too much about solving linear diophantine equations to be honest, I sorta am familiar with the Euclidean algorithm for GCD and I'm pretty decent with the idea of the Chinese remainder theorem, is that basically what kinds of skills it takes to solve this?

Answer 68

You know too much! they all are useful but none of them are needed to solve linear diophantine equaitons. We can simply use linearity

Answer 69

Haha ok. Two things I had discovered in the past few minutes are:

\[g(n)=n-1\] allows us to rewrite our problem as (which probably does us no good):
\[f(g(n))=g(f(n))\]

and the other thing was just playing around with is trying to control the coefficients that come down, but it still doesn't get around this adding 1 problem,

\(s\) is a square free number relatively prime to the other factors to the right of it.
\[n = s*\prod p_i^{a_ip_i}\]
\[f(n) = \prod a_ip_i^{a_ip_i}\]

So this means for numbers of this type,

\[f(n) = \frac{n}{s} \prod a_i\]

Answer 70

Its not hard to find one solution.
Suppose we know that \((144,23)\) is a solution to the diophantine equation \(3^3x = 13^2y+1\).

Then the null solution is given by \((13^2, 3^3)\).
All the solutions are given by \((x,y)=(144,23)+k(13^2,3^3)\), for \(k\in \mathbb{Z}\)

Answer 71

In summary, a possibly infinite set of solutions to the main equation in question are given by
\[n\equiv 3888 \pmod{4563}\]

\(\dfrac{n}{27}\) and \(\dfrac{n-1}{169}\) must be squarefree

Answer 72

All the solutions that I have provided earlier are based on above constraints

Answer 73

I understand that \(3^3*144=13^2*23+1\) however when I plug it in for the general solution it it looks like it should end up being like the null solution is:

\[(13^2,-3^3)\]

Answer 74

Ah nevermind, I did my math wrong I see exactly what you're saying now got it!

Answer 75

I see you have it !

Answer 76

Do you know any nice method to prune squarefree integers ?

Answer 77

Suppose I give you an infinite sequence of integers
is there a nice method to find squarefree integers among them ?

Answer 78

\[1-|\mu(n)|\]? Ok maybe not very useful lol.

Answer 79

Hmm, also not sure if this is helpful, but this is the sum of all square free integers (ok, clearly divergent):

\[\prod_i^\infty (1+p_i)\]

Answer 80

Any prime is a trivial squarefree integer.
\(\dfrac{n}{27}\) is squarefree whenever it is a prime. And we know that there are infinitely many primes of the form \(ax+b\) whenever \(\gcd(a,b)=1\).

Answer 81

that famous primes of form ax+b result is due to dirichlet

Answer 82

I have heard of this but only very very briefly and have no idea how you could prove this. But this is pretty impressive looking and simple so I like that.

Answer 83

proof is not so simple haha
http://mathworld.wolfram.com/DirichletsTheorem.html

Answer 84

ugh late for this :-\

Answer 85

The thing is we still haven't solved it though #_#

Answer 86

Boo ya