May 2021

tgan · 2021-05-02, 10:03

https://www.research.ibm.com/haifa/p...s/May2021.html

Walter · 2021-05-02, 12:30

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$ ?

LaurV · 2021-05-02, 13:51

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.

Walter · 2021-05-02, 14:44

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.

LaurV · 2021-05-02, 18:03

"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))

Walter · 2021-05-02, 18:43

Thanks, LaurV. 0scar also kindly explained it to me. This really confused me, but it is clear now.

SmartMersenne · 2021-05-02, 20:48

Also note that a_k can't be zero but can be m_k due to 1 <= a_k <= m_k

Dieter · 2021-05-03, 05:52

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.

slandrum · 2021-05-03, 14:08

Quote:

Originally Posted by Dieter

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.

Kebbaj · 2021-05-03, 18:12

Quote:

Originally Posted by Dieter

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.

Dr Sardonicus · 2021-05-04, 12:50

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.

2021-05-02, 10:03	#1
tgan Jul 2015 2·19 Posts	May 2021 https://www.research.ibm.com/haifa/p...s/May2021.html

2021-05-02, 13:51	#3
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 24051₈ Posts	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

2021-05-02, 18:03	#5
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 24051₈ Posts	"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))

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

2021-05-02, 12:30	#2
Walter "Walter S. Gisler" Sep 2020 Switzerland 3·5 Posts	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$ ?

2021-05-02, 14:44	#4
Walter "Walter S. Gisler" Sep 2020 Switzerland 3×5 Posts	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.

2021-05-02, 18:43	#6
Walter "Walter S. Gisler" Sep 2020 Switzerland 17₈ Posts	Thanks, LaurV. 0scar also kindly explained it to me. This really confused me, but it is clear now.

2021-05-02, 20:48	#7
SmartMersenne Sep 2017 2·73 Posts	Also note that a_k can't be zero but can be m_k due to 1 <= a_k <= m_k

2021-05-03, 05:52	#8
Dieter Oct 2017 139 Posts	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.

2021-05-04, 12:50	#11
Dr Sardonicus Feb 2017 Nowhere 14135₈ Posts	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.