The Necklace Problem Program

closed account (oG8qGNh0)
Directions: Use either DO-WHILE or WHILE loops. Solutions that avoid loops will receive NO POINTS. You must comment to explain the steps of your solutions.

Also – I very much suggest you have a sheet of scratch paper on which you work out the theory behind your solutions before you attempt to code this.

An interesting problem in number theory is sometimes called the “necklace problem.” This problem begins with two single-digit numbers. The next number is obtained by adding the first two numbers together and saving only the ones-digit. This process is repeated until the “necklace” closes by returning to the original two numbers. For example, if starting numbers are 1 and 8, twelve steps are required to close the “necklace”:

1 8 9 7 6 3 9 2 1 3 4 7 1 8

Write a program that asks the user for two starting numbers, and then displays the sequence and the number of steps taken. The program output should look similar to:

Enter the first number: 1
Enter the second number: 8
1 8 9 7 6 3 9 2 1 3 4 7 1 8
Your numbers required 12 steps.

Hint: To be able to check whether you are done, you will need to have saved copies of the original two numbers to match against. You will need a completely separate variable for counting. You may have extra in-between variables for moving through the problem.

My Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#include <iostream> 
using namespace std;

int main() 

{
int number;
cout << "Enter the first number: " ;
cin >> number;

int number2;
cout << " Enter the second number: " ;
cin >> number2;

sum = number + number2;

num=0

int number=12;


while

Any reccomendations on how this looks or what needs to be fixed?
Last edited on
Ganado (6862)
You're never going to learn anything by just copying other people's work.

Also, you were told how to format '''your''' code in a previous thread.
Hint, add:
[code]
   { your program here }
[/code]


(EDIT TO OTHERS: He removed his plagiarism after being called out)
Last edited on
closed account (oG8qGNh0)
what? I didn't copy
deleted account xyzzy (5768)
Source code from 8 years ago.....
https://answers.yahoo.com/question/index?qid=20130110085627AAWBRQ5

Evidence of copying? The idiotic _tmain() and the garbage #includes.
dutch (2548)
There are only 100 different inputs (0,0),(0,1),...,(9,9).
Strangely, the result and the number of such results are the same:

Result  Number
    1:      1      only (0,0)
    3:      3      only (0,5),(5,0),(5,5)
    4:      4      only (2,6),(4,2),(6,8),(8,4)
   12:     12
   20:     20
   60:     60

Here are all the 1's, 3's, and 4's:

(A,B): A  B  1  2  3  4
(0,0): 0, 0, 0
(0,5): 0, 5, 5, 0  5
(5,0): 5, 0, 5, 5, 0
(5,5): 5, 5, 0, 5, 5
(2,6): 2, 6, 8, 4, 2, 6
(4,2): 4, 2, 6, 8, 4, 2
(6,8): 6, 8, 4, 2, 6, 8
(8,4): 8, 4, 2, 6, 8, 4

Why are the number of results the same as the results?
Why only the results 1, 3, 4, 12, 20, 60?
lastchance (6980)
I don't know, @dutch, but if you call the first two terms a and b and start writing out the terms that follow you get a+b, a+2b, 2a+3b etc. (all mod 10). Then count the number of a's and b's and you will get
1,1,2,3,5,8... for a
1,2,3,5,8,13... for b
Fibonacci again!

The general nth term after the start is
cn=fna + fn+1b (mod 10)
where fn is the nth Fibonacci number.

So you are looking for n such that
cn-1=a
cn=b
Last edited on
seeplus (6637)
This is third time you're asked for help in writing code for your assignments - probably out of 3 assignments. Have you completed one assignment on your own yet?

Getting others to continuously write your code for you isn't going to help you learn. Asking for specific guidance over a particular point is one thing, but your posted code in the first post isn't even any attempt at completing the assignment.
closed account (oG8qGNh0)
Wait a sec, this is like the one time from the first one that I asked you to do the program... I m not asking you to finish it. Just asking how it is so far.
againtry (2313)
@naveenmmenon
Truth is none of us, even @lastchance and his spreadsheet, have even a remote idea on how to do this one. We have the same assignment and the deadline is close, so we are waiting on copying the answer from you. We're all in this together.
lastchance (6980)
dutch wrote:
Strangely, the result and the number of such results are the same:

Ah, no, that's not entirely strange.

Consider if you start 0 2, which requires 20 steps.
(0 2) 2 4 6 0 6 6 2 8 0 8 8 6 4 0 4 4 8 2 0 2


Think of this as a CYCLE of 20. For ANY consecutive pair on that cycle you must obtain THE SAME CYCLE, just starting in a different point on the cycle. So the number of such results can only be 20 or a multiple of 20 (if there are completely different length-20 cycles).

I think the only possible cycles are (UP TO A STARTING POINT):
(0 0) 0 - length 1 (type Even-Even)
(0 1) 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 3 3 6 9 5 4 9 3 2 5 7 2 9 1 0 1 - length 60 (type Odd-Odd-Even)
(0 2) 2 4 6 0 6 6 2 8 0 8 8 6 4 0 4 4 8 2 0 2 - length 20 (type Even-Even)
(0 5) 5 0 5 - length 3 (type Odd-Odd-Even)
(1 3) 4 7 1 8 9 7 6 3 9 2 1 3 - length 12 (type Odd-Odd-Even)
(2 6) 8 4 2 6 - length 4 (type Even-Even)

Since 1 + 60 + 20 + 3 + 12 + 4 = 100 ... that must be it.
Last edited on
seeplus (6637)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <iostream> 
using namespace std;

int main() 
{
    int number;
    cout << "Enter the first number: " ;
    cin >> number;

    int number2;
    cout << " Enter the second number: " ;
    cin >> number2;

    int sum = number + number2;
}


Any recomendations on how this looks


As the man said on the way down when falling off the roof of a high rise tower block - everything's good so far.....
Last edited on
dutch (2548)
lastchance wrote:
Think of this as a CYCLE of 20. For ANY consecutive pair on that cycle you must obtain THE SAME CYCLE, just starting in a different point on the cycle

You're right. It's not strange at all when you explain it like that!
dutch (2548)
The problem can be extended to 2 digit values (mod 100 instead of mod 10).
In that case there are 10000 initial inputs: (0,0),(0,1),...,(99,99).
The results and number of those results are not generally the same.
This must be because there are usually more than one unique "necklace".

  1:    1     (0,0)
  3:    3     (0,50),(50,0),(50,50)
  4:    4     (20,60),(40,20),(60,80),(80,40)
  6:   12     (0,25),(0,75),(25,0),(25,25),(25,50),(25,75),(50,25),(50,75),(75,0),(75,25),(75,50),(75,75)
 12:   60     ...
 20:  120
 60: 1800
100:  500
300: 7500

All the 6's:
  Type: (0,25)
   A  B  1  2  3  4  5  6
     0 25 25 50 75 25  0 25 
    25  0 25 25 50 75 25  0 
    25 25 50 75 25  0 25 25 
    25 50 75 25  0 25 25 50 
    50 75 25  0 25 25 50 75 
    75 25  0 25 25 50 75 25 
  Type: (0,75)
     A  B  1  2  3  4  5  6
     0 75 75 50 25 75  0 75 
    25 75  0 75 75 50 25 75 
    50 25 75  0 75 75 50 25 
    75  0 75 75 50 25 75  0 
    75 50 25 75  0 75 75 50 
    75 75 50 25 75  0 75 75 

              Types
  1:    1     1: ( 0, 0)
  3:    3     1: ( 0,50)
  4:    4     1: (20,60)
  6:   12     2: ( 0,25),( 0,75)
 12:   60     5: ( 5,15),( 5,40),( 5,90),(10,30),(15,70)
 20:  120     6: ( 0,20),( 4,12),( 4,32),( 4,52),( 8,24),(12,36)
 60: 1800    30: ( 0, 5),( 0,10),( 0,15),( 0,55),( 0,65),( 1, 3),( 1, 8),( 1,13),( 1,18),( 1,28),
                 ( 1,38),( 1,43),( 1,63),( 1,78),( 2, 6),( 2,16),( 2,21),( 2,26),( 2,31),( 3, 9),
                 ( 3,14),( 3,19),( 3,34),( 3,54),( 3,89),( 4,17),( 4,42),( 6,13),( 6,18),( 7,66)
100:  500     5: ( 0, 4),( 0, 8),( 0,12),( 0,24),( 0,36)
300: 7500    25: ( 0, 1),( 0, 2),( 0, 3),( 0, 6),( 0, 7),( 0, 9),( 0,11),( 0,13),( 0,17),( 0,18),
                 ( 0,19),( 0,21),( 0,22),( 0,23),( 0,34),( 0,51),( 0,53),( 0,57),( 0,59),( 0,61),
                 ( 0,63),( 0,67),( 0,69),( 0,71),( 0,73)

seeplus (6637)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
#include <iostream>

int main()
{
	int num1, num2;

	std::cout << "Enter first number: ";
	std::cin >> num1;
	num1 %= 10;

	std::cout << "Enter second number: ";
	std::cin >> num2;
	num2 %= 10;

	std::cout << num1 << "  " << num2 << "  ";

	int old1 = num1, old2 = num2;
	int steps = 0;
	do {
		const int newcur = (old1 + old2) % 10;
		std::cout << newcur << "  ";

		old1 = old2;
		old2 = newcur;
		++steps;
	} while (old1 != num1 || old2 != num2);

	std::cout << '\n' << steps << " steps\n";
}



Enter first number: 1
Enter second number: 8
1  8  9  7  6  3  9  2  1  3  4  7  1  8
12 steps

Enter first number: 2
Enter second number: 2
2  2  4  6  0  6  6  2  8  0  8  8  6  4  0  4  4  8  2  0  2  2
20 steps


This is rather trivial!

lastchance (6980)
dutch wrote:
The results and number of those results are not generally the same.
This must be because there are usually more than one unique "necklace".
  1:    1
  3:    3
  4:    4
  6:   12
 12:   60
 20:  120
 60: 1800
100:  500
300: 7500


Yes, it's a more interesting problem. The (number of results) still has to be a multiple of the (results) for the same reason as before - but for length 300 it's quite a substantial multiple.

Nice problem!
dutch (2548)
You can of course use any modulus. Here's a chart of moduli from 2 to 40, with the necklace length (across the top) and number of such necklaces:

    1   3   4   5   6   7   8   9  10  12  14  15  16  18  20  24  28  30  36  40  48  56  60  72  76  80  84 100 120
 2  1   1
 3  1                       1
 4  1   1           2
 5  1       1                                               1
 6  1   1                   1                                   1
 7  1                                               3
 8  1   1           2                   4
 9  1                       1                                   3
10  1   1   1                           1                   1                               1
11  1           2                  11
12  1   1           2       1                                   5
13  1                                                               6
14  1   1                                           3                               3
15  1       1               5                               1                   4
16  1   1           2                   4                       8
17  1                                                                       8
18  1   1                   1                                  13
19  1                           2                      19
20  1   1   1       2                   5                   1                               5
21  1                       1                      27
22  1   1       2                  11           2                      11
23  1                                                                              11
24  1   1           2       1           4                      21
25  1       1                                               6                                                   5
26  1   1                                                           6                                       6
27  1                       1                                   3                               9
28  1   1           2                               3                              15
29  1                   4                  58
30  1   1   1               5           1                   1   5               4           1                       4
31  1                                           2                      31
32  1   1           2                   4                       8                  16
33  1           2           1      11                                          24
34  1   1                                                                  32
35  1       1                                      15       1                                          12
36  1   1           2       1                                  53
37  1                                                                                              18
38  1   1                       8                      76
39  1                       1                                       6                  24
40  1   1   1       2                  25                   1                              21

Last edited on
lastchance (6980)
That's a pretty thorough piece of work, @dutch! I was trying some prime moduli. Most seem to have number of necklaces with the maximum length either 2*n or (n-1)/2; however, it's not a perfect fit.

I think your maximum necklace length in each case corresponds to the Pisano period; see:
https://en.wikipedia.org/wiki/Pisano_period
especially the first two tables.
Last edited on
Topic archived. No new replies allowed.