[superprismatic]

The value of the sequence 1, 2, 3, 5,

8, ... , where each member is the sum

of the two preceding, are reduced

mod N; i.e., if any value is greater

than N, N is subtracted. The

resulting sequence has period 26, and

the values, in numerical order, are

assigned to the letters A to Z. Note

that by this scheme the same number

may represent more than one letter.

The message, "Gardening is just a soil

sport," converted into numbers by this

process becomes: 3 0 89 1 2 34 5 34 3

/ 5 144 / 8 377 144 233 / 0 / 144 34

5 13 / 144 55 34 89 233. Find N.

SUPERPRISMATIC CORRECTION: "greater

than" should be "greater than or equal

to" in the explanation of "mod N" in

the first sentence. Walter Penney

was fallible.

[bushindo]

The value of the sequence 1, 2, 3, 5,

8, ... , where each member is the sum

of the two preceding, are reduced

mod N; i.e., if any value is greater

than N, N is subtracted. The

resulting sequence has period 26, and

the values, in numerical order, are

assigned to the letters A to Z. Note

that by this scheme the same number

may represent more than one letter.

The message, "Gardening is just a soil

sport," converted into numbers by this

process becomes: 3 0 89 1 2 34 5 34 3

/ 5 144 / 8 377 144 233 / 0 / 144 34

5 13 / 144 55 34 89 233. Find N.

SUPERPRISMATIC CORRECTION: "greater

than" should be "greater than or equal

to" in the explanation of "mod N" in

the first sentence. Walter Penney

was fallible.

I'm not sure that I understand the instruction in this puzzle. Is the following interpretation of the problem correct?

1) A number N is chosen, where N is larger than the largest number in the cipher code.

2) The fibonnaci series F(i) modulo N has a period of 26, meaning that for any index i, F(i) mod N == F(i + 26) mod N

3) The list of 26 values from within 1 period is sorted in ascending order, and each number assigned a letter according to its ordinal index (smallest number is A, second smallest is B, and so on).

4) This transformation is then applied to "Gardening is just a soil sport" to get ( 3 0 89 1 2 34 5 34 3/ 5 144 / 8 377 144 233 / 0 / 144 34 5 13 /144 55 34 89 233 )

5) Find N

PS. Also, does this sequence start at 1 or 0? Many references for the fibonnacci series start at 0.

Edited August 20, 2009 by bushindo

[Guest]

N = 521

A full period of the Fibonacci sequence modulo 521 is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 89, 466, 34, 500, 13, 513, 5, 518, 2, 520, 1

When placed in ascending order, you get

0, 1, 1, 1, 2, 2, 3, 5, 5, 8, 13, 13, 21, 34, 34, 55, 89, 89, 144, 233, 377, 466, 500, 513, 518, 520

Assigning to each letter,

A 0

B 1

C 1

D 1

E 2

F 2

G 3

H 5

I 5

J 8

K 13

L 13

M 21

N 34

O 34

P 55

Q 89

R 89

S 144

T 233

U 377

V 466

W 500

X 513

Y 518

Z 520

This is the correct key for encoding and decoding the text presented in the question.

Edited August 20, 2009 by mmiguel1

[superprismatic]

I'm not sure that I understand the instruction in this puzzle. Is the following interpretation of the problem correct?

1) A number N is chosen, where N is larger than the largest number in the cipher code.

2) The fibonnaci series F(i) modulo N has a period of 26, meaning that for any index i, F(i) mod N == F(i + 26) mod N

3) The list of 26 values from within 1 period is sorted in ascending order, and each number assigned a letter according to its ordinal index (smallest number is A, second smallest is B, and so on).

4) This transformation is then applied to "Gardening is just a soil sport" to get ( 3 0 89 1 2 34 5 34 3/ 5 144 / 8 377 144 233 / 0 / 144 34 5 13 /144 55 34 89 233 )

5) Find N

PS. Also, does this sequence start at 1 or 0? Many references for the fibonnacci series start at 0.

Your interpretation in 1 through 5 is correct. The sequence starts with 1, although that may not matter if 0, 1, 1 occurs in the 26-long cycle (because of your clarification #3). Also, if any number occurs more than once in the cycle, more than one letter is assigned to it.

[superprismatic]

N = 521

A full period of the Fibonacci sequence modulo 521 is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 89, 466, 34, 500, 13, 513, 5, 518, 2, 520, 1

When placed in ascending order, you get

0, 1, 1, 1, 2, 2, 3, 5, 5, 8, 13, 13, 21, 34, 34, 55, 89, 89, 144, 233, 377, 466, 500, 513, 518, 520

Assigning to each letter,

A 0

B 1

C 1

D 1

E 2

F 2

G 3

H 5

I 5

J 8

K 13

L 13

M 21

N 34

O 34

P 55

Q 89

R 89

S 144

T 233

U 377

V 466

W 500

X 513

Y 518

Z 520

This is the correct key for encoding and decoding the text presented in the question.

mmiguel1's got it!

[bushindo]

N = 521

A full period of the Fibonacci sequence modulo 521 is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 89, 466, 34, 500, 13, 513, 5, 518, 2, 520, 1

When placed in ascending order, you get

0, 1, 1, 1, 2, 2, 3, 5, 5, 8, 13, 13, 21, 34, 34, 55, 89, 89, 144, 233, 377, 466, 500, 513, 518, 520

Assigning to each letter,

A 0

B 1

C 1

D 1

E 2

F 2

G 3

H 5

I 5

J 8

K 13

L 13

M 21

N 34

O 34

P 55

Q 89

R 89

S 144

T 233

U 377

V 466

W 500

X 513

Y 518

Z 520

This is the correct key for encoding and decoding the text presented in the question.

Nice work. I'd like to know your approach, if you'd like to share.

[Guest]

Nice work. I'd like to know your approach, if you'd like to share.

I essentially brute forced it with a program I wrote in python.

I first wrote out all the letters of the alphabet and put the numbers given next to each one.

Since we are dealing with modulo N, we know that a number can never appear here that is larger than N.

Therefore N must be greater than 377.

For numbers in the Fibonacci sequence that are less than N, a modulo N operation will have no effect.

Therefore each of the numbers in the sequence before 377 must appear at least once.

You can definitely assign the letter M to 21 since it is the only possible place to put 21, and 21 was not given yet must appear at least once.

For letters like F, you cannot be sure if a 2 or a 3 belongs there.

There are 10 missing letters, and one duplicate (the 34), so you know the sequence continues 11 elements past 377.

To solve the problem, you should look at these numbers within the Fibonacci sequence, perform the modulo N operation on them,

and see if they can fill these categories without contradiction.

You can come up with groups of numbers that you should look for.

Since there are an A and a B slot, which are surrounded by a 0 and 1, we can define group 1;

Group 1 will keep count the 0's and 1's we get from the modulo N operation. There should be exactly 2.

Letters F and H are more of a problem since they share 3. If you find a 3, you cannot be sure of where to put it until you have

found a number satisfying the remaining letter.

We will make 3 different groups therefore, one to count 2's, one to count 3's, and one to count (4's and 5's).

Group 2 will count 2's. There should be at most 1 of these.

Group 3 will count 3's, The sum of the counts of group 2, group 3, and group 4 should not exceed 2.

Group 4 will contain 4's and 5's. There should be at most 1 of these.

Group 5 will contain a count of numbers found that lie between 55 and 89 inclusive (for the letter Q).

There should be 1 of these.

Group 6 will contain a count of numbers found that are equal or greater than 377.

There should be 5 of these.

Group 7 will account for the term that produces that duplicate 34.

It will count the number of 34's. There should be exactly one of these.

I first generated the first 26 numbers in the Fibonacci sequence.

I then selected a range of numbers to test N for. If I don't find anything at first, I can make this range wider to cover more numbers.

For each of these N, I go through the latter 11 (I think) numbers in my generated list of Fibonacci numbers (the ones greater than 377) and take the number modulo N. I classify the number into one of the groups mentioned above and increase the counter of that group by 1. If it does not fit into any of those groups, we move on to the next N since that N is incompatible with the key.

I then check to see if any of the groups grew too large (Group 1's count exceeding 2 for example, or group 6 exceeding 5).

If any of those conditions fail, we move on to the next N.

If we can get through all 11 numbers from the Fibonacci sequence without breaking any of these rules, it is very likely we have found the right solution. The program stops and informs me of a potential match. I then double check everything and there we go, we have an answer. It just happened to be 521.

Edited August 21, 2009 by mmiguel1

[bushindo]

I essentially brute forced it with a program I wrote in python.

I first wrote out all the letters of the alphabet and put the numbers given next to each one.

Since we are dealing with modulo N, we know that a number can never appear here that is larger than N.

Therefore N must be greater than 377.

For numbers in the Fibonacci sequence that are less than N, a modulo N operation will have no effect.

Therefore each of the numbers in the sequence before 377 must appear at least once.

You can definitely assign the letter M to 21 since it is the only possible place to put 21, and 21 was not given yet must appear at least once.

For letters like F, you cannot be sure if a 2 or a 3 belongs there.

There are 10 missing letters, and one duplicate (the 34), so you know the sequence continues 11 elements past 377.

To solve the problem, you should look at these numbers within the Fibonacci sequence, perform the modulo N operation on them,

and see if they can fill these categories without contradiction.

You can come up with groups of numbers that you should look for.

Since there are an A and a B slot, which are surrounded by a 0 and 1, we can define group 1;

Group 1 will keep count the 0's and 1's we get from the modulo N operation. There should be exactly 2.

Letters F and H are more of a problem since they share 3. If you find a 3, you cannot be sure of where to put it until you have

found a number satisfying the remaining letter.

We will make 3 different groups therefore, one to count 2's, one to count 3's, and one to count (4's and 5's).

Group 2 will count 2's. There should be at most 1 of these.

Group 3 will count 3's, The sum of the counts of group 2, group 3, and group 4 should not exceed 2.

Group 4 will contain 4's and 5's. There should be at most 1 of these.

Group 5 will contain a count of numbers found that lie between 55 and 89 inclusive (for the letter Q).

There should be 1 of these.

Group 6 will contain a count of numbers found that are equal or greater than 377.

There should be 5 of these.

Group 7 will account for the term that produces that duplicate 34.

It will count the number of 34's. There should be exactly one of these.

I first generated the first 26 numbers in the Fibonacci sequence.

I then selected a range of numbers to test N for. If I don't find anything at first, I can make this range wider to cover more numbers.

For each of these N, I go through the latter 11 (I think) numbers in my generated list of Fibonacci numbers (the ones greater than 377) and take the number modulo N. I classify the number into one of the groups mentioned above and increase the counter of that group by 1. If it does not fit into any of those groups, we move on to the next N since that N is incompatible with the key.

I then check to see if any of the groups grew too large (Group 1's count exceeding 2 for example, or group 6 exceeding 5).

If any of those conditions fail, we move on to the next N.

If we can get through all 11 numbers from the Fibonacci sequence without breaking any of these rules, it is very likely we have found the right solution. The program stops and informs me of a potential match. I then double check everything and there we go, we have an answer. It just happened to be 521.

Thanks for the detailed description. It's good to see a fellow Python user on the forum. And a better welcome to the forum, by the way.

Edited August 21, 2009 by bushindo

[Guest]

Thanks for the detailed description. It's good to see a fellow Python user on the forum. And a better welcome to the forum, by the way.

Thanks!

[Guest]

Well, you know 55 ≤ 610-N ≤ 89. That means 521 ≤ N ≤ 555. I guessed and checked from there (luckily 521 was the answer).

I like doing math by hand (viz. limited calculator, no computer, etc), but didn't know how to finish this one correctly (without guess and check). Can anyone help me with that?