Pre-Q&A

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
Q3. Find \(\displaystyle \sum_{n=1}^{2520}\gcd(n,2520).\)

Bonus: Do it without using a computer.
 

Hoempa

Math Team
Apr 2010
2,780
361
2520 = 2^3 * 3^2 * 5 * 7
Let \(\displaystyle \text{gcdsum}(n) = \sum_{i=1}^n \gcd(i, n)\)

I get
\(\displaystyle \text{gcdsum}(p^k) = (p \cdot (k + 1) - k) p^{k-1}\)
for prime p and positive integer k.

and
\(\displaystyle \text{gcdsum} \left(\prod_{i=1}^n p_i^{\;e_i}\right) = \prod_{i=1}^n \text{gcdsum} \left(p_i^{\;e_i} \right)\)
Where \(\displaystyle \prod_{i=1}^n p_i^{\;e_i}\) is a prime factorisation.

Therefore
\(\displaystyle \text{gcdsum}(2520) = \sum_{i=1}^{2520} \gcd(i, 2520) = \\\text{gcdsum}(2^3) \cdot \text{gcdsum}(3^2) \cdot \text{gcdsum}(5) \cdot \text{gcdsum}(7) = 20 \cdot 9 \cdot 21 \cdot 13\\ = 49140\)

I found no counterexample for the above statements and Pari says 49140 as well.
Is my method correct?
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
Yes, excellent! I chose that number to be convenient for hand-calculation with that method.

(Anyone, feel free to post questions at any time.)

Q4. How many positive integers less than 100 can be written in the form m/n where m and n are products of nonzero Fibonacci numbers?
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
Oh, and I can't resist posting this one, even though I don't have an answer myself:

Q5. Why are all terms of A234566 integers?
 

johnr

Math Team
Apr 2012
1,579
22
Messing with the Fibonacci question empirically cost me hours of sleep! The more I sought, the more I found. Anyone get anywhere interesting with it?
 
Sep 2012
764
53
British Columbia, Canada
CRGreathouse said:
Why are all terms of A234566 integers?
Well, if they weren't all integers, then it wouldn't be a sequence in the OEIS then!
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
johnr said:
Messing with the Fibonacci question empirically cost me hours of sleep! The more I sought, the more I found. Anyone get anywhere interesting with it?
Well, two key components are that the Fibonacci sequence is a gcd sequence: gcd(F(m), F(n)) = F(gcd(m, n)) and that Fibonacci numbers greater than, uh, 144 have a primitive prime divisor: p | F(n) but p does not divide F(m) for 0 < m < n. So sometimes you find that two factors are 'stuck together' for Fibonacci sequences and you can't get them apart, which means you can't make those numbers separately.

As usual there is an OEIS sequence spoiling the answer further if you care to look.
 

agentredlum

Math Team
Jul 2011
3,372
234
North America, 42nd parallel
Please allow me to post a question.

Q. Find a relation between primes that generates the first 31 numbers in the following integer sequence

1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 ...

Bonus Question: Why is this sequence not in OEIS?

If no one gets it in 24 hours i will post the answer unless someone asks for more time or asks for a hint.

:D
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
agentredlum said:
Please allow me to post a question.
Yes, please!

agentredlum said:
Q. Find a relation between primes that generates the first 31 numbers in the following integer sequence

1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 ...
Well, my first guess would be that this is an indicator sequence representing the primes 2, 3, 5, 13, 17, 113, ....

If so, I might further guess that this is related to prime gaps, since 113 is the first prime before a record gap (the next prime is 113 + 14 = 127). But I can't get any further, even if both are right.
 

agentredlum

Math Team
Jul 2011
3,372
234
North America, 42nd parallel
CRGreathouse said:
agentredlum said:
Q. Find a relation between primes that generates the first 31 numbers in the following integer sequence

1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 ...
Well, my first guess would be that this is an indicator sequence representing the primes 2, 3, 5, 13, 17, 113, ....
Thank you for participating! From the primes you give above , only 17 and one more prime are represented in the sequence. I don't want to say too much yet for fear of making it too easy , but of course i will be happy to say more if you or anyone else asks.

CRGreathouse said:
If so, I might further guess that this is related to prime gaps, since 113 is the first prime before a record gap (the next prime is 113 + 14 = 127). But I can't get any further, even if both are right.
I don't think it is related to prime gaps in the usual sense , for example , the prime gap between 23 and 29 is 6 because 29 - 23 = 6 (I personally disagree with the definition but that's niether here nor there :mrgreen:)

But it may be related to prime gaps of another form which will become apparent once the rule for writing down 0's and 1's is discovered.

Note: The sequence consists entirely of 0's and 1's.

:D