/sci/ - Science & Math » Thread #10497705

33KiB, 1411x170, day_22-problem.png

View Same Google iqdb SauceNAO

Putnam Problem of the Night

http://math.harvard.edu/putnam/ Tue 26 Mar 06:40:03 2019 No.10497705 View Reply Original Report

Quoted By: >>10499353 >>10502678

$ \text{For each positive integer }n\text{, write the sum }\sum_{m=1}^n 1/m\text{ in the form }p_n/q_n\text{, where } \\ p_n\text{ and }q_n\text{ are relatively prime positive integers. Determine all }n\text{ such that 5} \\ \text{does not divide }q_n\text{.} $

http://math.harvard.edu/putnam/

http://math.harvard.edu/putnam/ Tue 26 Mar 2019 06:41:24 No.10497706 Report

Quoted By:

Previous Thread >>10495275

Anonymous

Anonymous Tue 26 Mar 2019 11:21:43 No.10497987 Report

Quoted By: >>10498087

What's the point if there's no anime girl to encourage me?

Anonymous

View Same Google iqdb SauceNAO WeightyNastyAnglerfish-max-1mb.gif, 889KiB, 280x275

Anonymous Tue 26 Mar 2019 12:12:25 No.10498087 Report

Quoted By: >>10500211

>>10497987
Chika be your guide, fellow patrician.

Anonymous

Anonymous Tue 26 Mar 2019 12:13:22 No.10498088 Report

Quoted By:

wheres the fucking anime

Anonymous

Anonymous Tue 26 Mar 2019 21:32:31 No.10499353 Report

Quoted By: >>10499475

>>10497705

looks like it's just n=1,2,3,4. bump in case it comes to me later. for n=5 it's 137/60.

i tried an inductive proof and other things along that line but i can't see how you'd show that, after finding the LCD and adding (pn/qn + 1/(n+1)), the numerator would have fewer 5's in its prime factorization than the denominator.

Anonymous

Anonymous Tue 26 Mar 2019 22:05:29 No.10499475 Report

Quoted By: >>10499646

>>10499353
That's because it's wrong. A quick program shows this not to be the case

Anonymous

Anonymous Tue 26 Mar 2019 22:56:24 No.10499646 Report

Quoted By: >>10499673

>>10499475

mind sharing your counterexample?

Anonymous

Anonymous Tue 26 Mar 2019 23:06:09 No.10499673 Report

Quoted By: >>10500004 >>10500418 >>10501587

>>10499646
Smallest counterexample is 20: the sum yields 55835135/15519504.
Here is a python. You can check by varying the bound N that there does not seem to be a largest n:

def gcd(a,b):
if a < b:
return gcd(b,a);
else:
if b == 0:
return a;
else:
return gcd(b, a%b);
N = 100;
p, q, d = 1, 1, 1;
for n in range(1, N):
p, q = (n+1)*p + q, (n+1)*q;
d = gcd(p,q);
p, q = p/d, q/d;
if q%5 != 0:
print(n+1);

Anonymous

Anonymous Wed 27 Mar 2019 01:47:39 No.10500004 Report

Quoted By:

>>10499673
>there does not seem to be a largest n

makes sense. though, the wording of the question made it seem like we were dealing with a finite set of n where 5 | qn, rather than trying to characterize an infinite set

Anonymous

Anonymous Wed 27 Mar 2019 03:16:44 No.10500137 Report

Quoted By: >>10500191

I can not guarantee that these are all the $n$ , but all $n$ found this way will satisfy the requirement.

Write $n! = 5^kC$ , then all $n$ such that $\sum_{m=1}^{\left\lfloor{\frac{n}{5}}\right\rfloor}\frac{n!}{5m} = \frac{n!}{5} + \frac{n!}{10} + \frac{n!}{15} + \cdots + \frac{n!}{n} = 5^jD$ where $j\geq n$ will satisfy the requirement.

For example, for n = 10 we have that n! = 5^2*C, while the sum gives something that factors into 5*D, so it doesn't satisfy our condition.

This becomes unfeasible to compute after about n = 100, but so far it has found all correct n, and haven't missed any. But since the n laying after 124 is at least above 6000 I can't be sure. Unfortunately even with that formula the sum becomes way too big for me to handle accurately, with my limited programming skills.

Anonymous

Anonymous Wed 27 Mar 2019 03:50:58 No.10500191 Report

Quoted By: >>10500206 >>10500227

>>10500137
I'll throw in a conjecture I have, namely that it is enough to check whether or not $5\nmid q_n$ in
$\frac{1}{5} + \frac{1}{10} + \frac{1}{15} + \cdots + \frac{1}{n} = \frac{p_n}{q_n}$
and if so this n satisfies the requirement.

Anonymous

Anonymous Wed 27 Mar 2019 03:52:10 No.10500195 Report

Quoted By: >>10500495 >>10501587 >>10501983

https://en.wikipedia.org/wiki/P-adic_order
Let m = v_5(p_n/q_n) and t = v_5(n+1).

Case 1: m>0
v_5(p_(n+1)) = 0, v_5(q_(n+1)) = t

Case 2: m=0
Case 2a: t>0
v_5(p_(n+1)) = 0, v_5(q_(n+1)) = t

Case 2b: t=0
v_5(p_(n+1)) = ?, v_5(q_(n+1)) = 0

Case 3: m<0
Case 3a: t != |m|
v_5(p_(n+1)) = 0, v_5(q_(n+1)) = max(t, |m|)

Case 3b: t=|m|
v_5(p_(n+1)) = ?, v_5(q_(n+1)) = ?

Obviously Case 3b is the only case where 5 can divide q_n and not divide q_(n+1).

Anonymous

Anonymous Wed 27 Mar 2019 03:53:41 No.10500198 Report

Quoted By: >>10500242

What does it mean to be a "relatively" prime positive integer?

Anonymous

Anonymous Wed 27 Mar 2019 04:00:03 No.10500206 Report

Quoted By:

>>10500191
Jesus I just realized this is just a fifth of the harmonic series. I'm too tired for this.

Anonymous

Anonymous Wed 27 Mar 2019 04:01:56 No.10500211 Report

Quoted By:

>>10498087
anon.. please don't tell me you're not single

Anonymous

Anonymous Wed 27 Mar 2019 04:14:33 No.10500227 Report

Quoted By: >>10500279 >>10501587

>>10500191
So you need to know if v_5(p_floor(n/5)) <1 or not.
I have a slick formula that might help.

$Let\ \hat{H}_n = \sum\limits_{m=1 \ 5 \nmid m}^n 1/m = H_n - {1 \over 5} H_{\left \lfloor{n/5}\right \rfloor}. \\ H_n = \sum\limits_{t=0}^{\left \lfloor{log_5(n)}\right \rfloor} 5^{-t}\hat{H}_{\left \lfloor{n/5^t}\right \rfloor}.$

Anonymous

Anonymous Wed 27 Mar 2019 04:22:30 No.10500242 Report

Quoted By:

>>10500198

the gcd of it (the number) and some other particular number (given) is 1. That is, they have no common factors.

A number is not, of itself, "relatively prime". This phrase describes a relationship which the number has (or does not have) with another number

Anonymous

Anonymous Wed 27 Mar 2019 04:41:31 No.10500279 Report

Quoted By:

>>10500227
Since no terms in H hat are divisible by 5, you could look at the sum mod 5.

Anonymous

Anonymous Wed 27 Mar 2019 06:06:18 No.10500418 Report

Quoted By: >>10500495

>>10499673
Did you scan low value integers for a counterexample or did you find it methoditcally?

Anonymous

Anonymous Wed 27 Mar 2019 06:58:47 No.10500495 Report

Quoted By:

>>10500418
He probably just ran his program.

From >>10500195
You really only need to look at what happens for n = 5k.
If 5 divides q exactly m times for n = 5k, 5 will divide q exactly m times for n = 5k+1,5k+2,5k+3,5k+4.

If v_5(q_(5k-5)) != v_5(5k) then v_5(q_5k) = max{ v_5(q_(5k-5)), v_5(5k) }.

The only way q MIGHT lose some 5's is when v_5(q_(5k-5)) = v_5(5k).

Anonymous

Anonymous Wed 27 Mar 2019 15:07:04 No.10501188 Report

Quoted By: >>10501296

can someone explain exactly what this question is asking for?

if there are infinite n that satisfy this requirement, then what do they mean by "determine all n"?

the set is already defined in the question, and its elements can be enumerated procedurally by brute force.

are we trying to find some closed-form mapping from from N to this subset of N? a better procedure than just brute force checking?

Anonymous

Anonymous Wed 27 Mar 2019 15:47:29 No.10501296 Report

Quoted By: >>10502560 >>10502565

>>10501188
There's probably a simple formula.
>the set is already defined in the question, and its elements can be enumerated procedurally by brute force.
If there are infinitely many n, good luck brute forcing them.
If you don't know if there are infinitely many n, good luck with the halting problem.

I think you've missed the point of math entirely.

Anonymous

Anonymous Wed 27 Mar 2019 17:41:46 No.10501587 Report

Quoted By: >>10501647

>>10500227
$Let\ \hat{H}_k = {\hat{p}_k \over \hat{q}_k}.\\ Clearly\ 5 \nmid \hat{q}_k.\\ H_{5k} = \hat{H}_{5k} + {1 \over 5}H_k = {\hat{p}_{5k} \over \hat{q}_{5k}} + {p_k \over 5q_k}\\ = {5q_k\hat{p}_{5k}+p_k\hat{q}_{5k} \over 5q_k\hat{q}_{5k}}.\\ If\ 5\nmid p_k\ then\ v_5(q_{5k})= 1+v_5(q_k).\\ If\ 5|p_k\ then\ v_5(q_{5k})=0.$

Since H_4 = 25/12 you know 5 doesn't divide q_20. (the smallest counterexample given in >>10499673)

Using cases 1 and 2 from >>10500195
if you know 5 doesn't divide q_5k (m>=0) then you know it doesn't divide q_5k+1,q_5k+2,q_5k+3,q_5k+4.

Using case 3a from >>10500195
if you know 5 divides q_5k then you know it divides q_5k+1,q_5k+2,q_5k+3,q_5k+4.

Using cases 1 and 2a from >>10500195
you know there can't be two adjacent groupings of 5 that aren't divisible by 5.

If you can understand how the groupings generated by H_4 behave, the problem will be solved.
This will probably involve understanding how p_k behaves.

Anonymous

Anonymous Wed 27 Mar 2019 18:07:39 No.10501647 Report

Quoted By: >>10501983

>>10501587
I'm a dummy and I'm at a loss about any of this. Which path do I take ton find you? I mean. What math topics can help me find you? And just what is all this for? ROCKET SCIENCE? PROGRAMMING? Just what is it all for? Please help me. I want to be more than I am. Where do I begin?

Anonymous

Anonymous Wed 27 Mar 2019 20:27:59 No.10501983 Report

Quoted By: >>10502125

>>10501647
Quit making it seem harder than it is.
All of >>10500195 comes from looking at
p_n/q_n +1/(n+1) and figuring out what happens when 5 divides, p_n, q_n, or n+1.
Understanding how H_n+1 behaves based on H_n seems like a rational thing to do.
The only "clever" part is
$H_{5k} = \hat{H}_{5k} + {1 \over 5}H_k$

Anonymous

Anonymous Wed 27 Mar 2019 21:11:24 No.10502125 Report

Quoted By:

>>10501983
As a Bainlet I have no idea so I'm gonna copy and paste all you guys said and Google it. Or maybe I'll start with khan Academy like I read in another thread. I don't want to lose sight of the beauty I'm seeing here. It's an ocean, all of it. But I'm getting refreshed just enjoying the ambient water spray I'm getting from this thread. It's like watching wizards contemplate spells. It's all so fascinating to me. I'm too dumb!!!

Anonymous

Anonymous Wed 27 Mar 2019 21:27:02 No.10502146 Report

Quoted By:

WHat should I know if I want to solve this kind of problem?

Anonymous

Anonymous Thu 28 Mar 2019 00:15:18 No.10502560 Report

Quoted By:

>>10501296
>I think you've missed the point of math entirely.

no, it's a badly worded question written by someone with a marginal grasp of english or someone who thinks i'm a mind reader.

Anonymous

View Same Google iqdb SauceNAO tf.jpg, 36KiB, 474x474

Anonymous Thu 28 Mar 2019 00:16:37 No.10502565 Report

Quoted By: >>10502577

>>10501296
>I think you've missed the point of math entirely.

no, it's a badly worded question written by someone with a marginal grasp of english or someone who thinks i'm a mind reader.

Anonymous

View Same Google iqdb SauceNAO 1467307786346.jpg, 62KiB, 444x563

Anonymous Thu 28 Mar 2019 00:21:28 No.10502577 Report

Quoted By: >>10502589

>>10502565
its worded totally fine, retard

Anonymous

Anonymous Thu 28 Mar 2019 00:27:50 No.10502589 Report

Quoted By: >>10502713

>>10502577

it's not worded totally fine. they seem to be asking for an alternate description for that infinite set, or perhaps an efficient procedure for enumerating them, but that's not what the question says.

Anonymous

Anonymous Thu 28 Mar 2019 01:15:54 No.10502678 Report

Quoted By:

>>10497705
This is one of the hardest putnam questions.
1997 B3 for anyone who wants to google it.

Anonymous

Anonymous Thu 28 Mar 2019 01:32:44 No.10502713 Report

Quoted By: >>10502725

>>10502589
>they seem to be asking for an alternate description for that infinite set
the answer is actually a finite set

Anonymous

Anonymous Thu 28 Mar 2019 01:36:04 No.10502725 Report

Quoted By:

>>10502713

oh, alright then.

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches