mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)

 tgan 2021-05-02 10:03

May 2021

[url]https://www.research.ibm.com/haifa/ponderthis/challenges/May2021.html[/url]

 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 [TEX]n[/TEX], we have that for some [TEX]k[/TEX], [TEX]n[/TEX] is equivalent to [TEX]a_k[/TEX] modulo [TEX]m_k[/TEX] (i.e. [TEX]m_k[/TEX] divides [TEX]n-a_k [/TEX]).

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

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: [TEX]A_{m+n} = A_mF_{n-1} + A_{m+1}F_n[/TEX] .

And this one: [TEX]A_{m+n+1} = A_mF_{n-1} + A_{m+1}F_n[/TEX] ?

 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 :razz:

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. :picard: 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" :razz: (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=Dieter;577502]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.[/QUOTE]

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=Dieter;577502]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.[/QUOTE]

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 :big grin:

The condition that the initial terms be relatively prime seems to have been assumed, but should have been stated.

 Kebbaj 2021-05-04 14:34

[QUOTE=Kebbaj;577554]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.[/QUOTE]

Sorry, in my answer, I meant if A0 and A1 are not coprime then the sequence would be trivial.

 uau 2021-05-04 16:45

[QUOTE=Dr Sardonicus;577605]The condition that the initial terms be relatively prime seems to have been assumed, but should have been stated.[/QUOTE]
The sentence "Our goal is to see how to generate a Fibonacci-like sequence without any prime numbers." would make more sense if it ruled out the obvious and trivial common factors solution. But I don't think this affects the problem itself - the stated requirement is to find a set of tuples, not just A0 and A1, so the lack of the condition doesn't make much difference. Given the form of the required answer, it doesn't seem to allow any trivial solution that would otherwise be forbidden.

 Dieter 2021-05-05 08:04

The text of the challenge is updated.

1) F_0 = 0
2) It's explicitly formulated that A_0 and A_1 have to be relatively prime.

 Walter 2021-05-05 11:48

I believe I have solved the first part of the problem. I.e. I have a set of T triplets that satisfy the conditions 1-4.

However, I am a bit confused by the second part:

[QUOTE]Given this set, one can generate [TEX]A_0[/TEX] and [TEX]A_1[/TEX] that satisfy
[TEX]A_0[/TEX] is equivalent to [TEX]F_{m_k-a_k} modulo p_k[/TEX]
[TEX] A_1[/TEX] is equivalent to [TEX] F_{m_k-a_k+1} modulo p_k[/TEX][/QUOTE]

Should there be a [TEX]A_0[/TEX] and [TEX]A_1[/TEX] that satisfies this for every [TEX]k[/TEX]? Or is it sufficient if it is satisfied for one [TEX]k[/TEX]? The problem specification isn't so clear about this, or am I missing something? I haven't checked my solution in detail yet, but currently, my intuition is that there isn't a pair of [TEX]A_0[/TEX] and [TEX]A_1[/TEX] that satisfies it for all k in my solution.

 Dr Sardonicus 2021-05-05 12:06

[QUOTE=Walter;577696][QUOTE]Given this set, one can generate [TEX]A_0[/TEX] and [TEX]A_1[/TEX] that satisfy
[TEX]A_0[/TEX] is equivalent to [TEX]F_{m_k-a_k} modulo p_k[/TEX]
[TEX] A_1[/TEX] is equivalent to [TEX] F_{m_k-a_k+1} modulo p_k[/TEX][/QUOTE]Should there be a [TEX]A_0[/TEX] and [TEX]A_1[/TEX] that satisfies this for every [TEX]k[/TEX]?[/quote]Yes. Using the condition that the p[sub]k[/sub] are distinct, the existence of simultaneous solutions to all the congruences is guaranteed by the Chinese Remainder Theorem (CRT).

 Walter 2021-05-05 17:13

[QUOTE=Dr Sardonicus;577698]Yes. Using the condition that the p[sub]k[/sub] are distinct, the existence of simultaneous solutions to all the congruences is guaranteed by the Chinese Remainder Theorem (CRT).[/QUOTE]

Ah, right. That makes perfect sense.

 Kebbaj 2021-05-15 20:14

The error of ak condition (1.) is always in the text even after the update? ak can take the value 0. !!

ak =0 is equivalent to ak = 60 but the condition 1 limits ak to the maximum of mk.

On other hand i try to have a matrix of less than 17 elements triplets, but it may be impossible?

 All times are UTC. The time now is 02:41.