mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2021-05-02, 10:03   #1
tgan
 
Jul 2015

111002 Posts
Default May 2021

https://www.research.ibm.com/haifa/p...s/May2021.html
tgan is offline   Reply With Quote
Old 2021-05-02, 12:30   #2
Walter
 
"Walter S. Gisler"
Sep 2020
Switzerland

10112 Posts
Default

I believe there are some mistakes in the problem statement, can anyone confirm this?

1.
For every natural number n, we have that for some k, n is equivalent to a_k modulo m_k (i.e. m_k divides n-a_k ).

Shouldn't this be: For every natural number n, we have that for some k, a_k is equivalent to n modulo m_k

2.
one can prove that this sequence does not contain any primes by using the following easy-to-prove identity, which holds for any Fibonacci-like sequence: A_{m+n} = A_mF_{n-1} + A_{m+1}F_n .

And this one: A_{m+n+1} = A_mF_{n-1} + A_{m+1}F_n ?
Walter is offline   Reply With Quote
Old 2021-05-02, 13:51   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

980810 Posts
Default

Isn't (1) the same either way?

My "argument" with them is F0=1, which is wrong. Everybody knows F0=0 (otherwise the "only prime indexes can be prime" won't hold). In fact, how I always remember it is that the 5th fibo number is 5

In fact, they say as much, further when affirming that F3=2 and F11=89. If F0=1, those would be false.

Last fiddled with by LaurV on 2021-05-02 at 14:06
LaurV is offline   Reply With Quote
Old 2021-05-02, 14:44   #4
Walter
 
"Walter S. Gisler"
Sep 2020
Switzerland

1110 Posts
Default

Ah, you are right. I had missed that F0 = 1. With that, 2 is indeed correct.

Regarding (1), I am pretty sure it isn't the same either way.

m_k >= a_k, hence a_k mod m_k is either 0 or a_k , so with a set of triplets that is limited in size, a_k mod m_k couldn't be any natural number.
Walter is offline   Reply With Quote
Old 2021-05-02, 18:03   #5
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24·613 Posts
Default

"a (mod m)" is defined as the reminder (an integer number between 0 and m-1, inclusive) that is left when you divide a to m, therefore, a\(\equiv\)b (mod m) is the same as b\(\equiv\)a (mod m), those are "equivalence classes", not numbers, it is just that we are lazy and don't write the "hats" (i.e. \(\hat{a} \equiv \hat{b}\) (mod m))
LaurV is offline   Reply With Quote
Old 2021-05-02, 18:43   #6
Walter
 
"Walter S. Gisler"
Sep 2020
Switzerland

B16 Posts
Default

Thanks, LaurV. 0scar also kindly explained it to me. This really confused me, but it is clear now.
Walter is offline   Reply With Quote
Old 2021-05-02, 20:48   #7
SmartMersenne
 
Sep 2017

2×59 Posts
Default

Also note that a_k can't be zero but can be m_k due to 1 <= a_k <= m_k
SmartMersenne is offline   Reply With Quote
Old 2021-05-03, 05:52   #8
Dieter
 
Oct 2017

7916 Posts
Default

Have A_0 and A_1 to be relatively prime? He didn't write it.
Otherwise A_0 = 4 and A_1 = 6 yielded a Fibonacci-like sequence without primes.
But that cannot be the challenge.
Dieter is offline   Reply With Quote
Old 2021-05-03, 14:08   #9
slandrum
 
Jan 2021
California

3668 Posts
Default

Quote:
Originally Posted by Dieter View Post
Have A_0 and A_1 to be relatively prime? He didn't write it.
Otherwise A_0 = 4 and A_1 = 6 yielded a Fibonacci-like sequence without primes.
But that cannot be the challenge.
That was just the start of it, you need to read the rest of the requirements of the series to see if the series you made meets the other requirements.
slandrum is offline   Reply With Quote
Old 2021-05-03, 18:12   #10
Kebbaj
 
Kebbaj's Avatar
 
"Kebbaj Reda"
May 2018
Casablanca, Morocco

1368 Posts
Default

Quote:
Originally Posted by Dieter View Post
Have A_0 and A_1 to be relatively prime? He didn't write it.
Otherwise A_0 = 4 and A_1 = 6 yielded a Fibonacci-like sequence without primes.
But that cannot be the challenge.
If A0 and A1 are coprime, the sequance would be trivial: “easy common factor of the sequence with no prime “. So for the sequence to be interesting it is essential that A0 and A1 would be coprime.
GCD[A0,A1] must be = 1.

I think that the webmaster did not write the relation of divisiblity between A0 and A1 because the question was to find a sequence of triplets with the conditions quoted 1 to 4 ”and the A0 A1 are simply to explain the goal of the question.

Last fiddled with by Kebbaj on 2021-05-03 at 18:18
Kebbaj is offline   Reply With Quote
Old 2021-05-04, 12:50   #11
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

19·269 Posts
Default

The May 2021 Challenge seems quite similar to finding Riesel or Sierpinski numbers by means of "covering sets" of congruences.

The misstatement of the subscripts is the kind of oopsadaisy a number theorist might make

The condition that the initial terms be relatively prime seems to have been assumed, but should have been stated.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
April 2021 Xyzzy Puzzles 25 2021-05-04 22:37
March 2021 tgan Puzzles 0 2021-02-28 13:30
January 2021 tgan Puzzles 36 2021-02-09 21:29
February 2021 Xyzzy Puzzles 11 2021-02-04 14:53

All times are UTC. The time now is 06:00.


Mon Nov 29 06:00:39 UTC 2021 up 129 days, 29 mins, 0 users, load averages: 1.17, 1.08, 1.13

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.