perplexus.info :: Algorithms : Sequence of Musical Tones

Sequence of Musical Tones (Posted on 2004-12-14)

Music on the planet Alpha Lyra IV consists of only two notes, called A and B. Also, songs never include three consecutive repetitions of any sequence nor does BB ever occur. A sequence of notes can have 1 or more notes in it.

What is the longest song on Alpha Lyra IV?

See The Solution Submitted by Erik O.

Rating: 3.8333 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

computer solution

| Comment 4 of 20 |

The 110 songs that can be produced are:

a
ab
aba
abab
ababa
ababaa
ababaab
ababaaba
ababaabab
ababaababa
ababaababaa
ababaababaab
ababaababaaba
ababaababaabab
ababaababaabaa
ababaababaabaab
ababaabaa
ababaabaab
abaa
abaab
abaaba
abaabab
abaababa
abaababaa
abaababaab
abaababaaba
abaababaabab
abaababaababa
abaababaababaa
abaababaabaa
abaababaabaab
abaabaa
abaabaab
aa
aab
aaba
aabab
aababa
aababaa
aababaab
aababaaba
aababaabab
aababaababa
aababaababaa
aababaababaab
aababaababaaba
aababaababaabaa
aababaababaabaab
aababaabaa
aababaabaab
aabaa
aabaab
aabaaba
aabaabab
aabaababa
aabaababaa
aabaababaab
aabaababaaba
aabaababaabab
aabaababaababa
aabaababaababaa
aabaababaabaa
aabaababaabaab
aabaabaa
b
ba
bab
baba
babab
babaa
babaab
babaaba
babaabab
babaababa
babaababaa
babaababaab
babaababaaba
babaababaabab
babaababaababa
babaababaabaa
babaababaabaab
babaabaa
babaabaab
baa
baab
baaba
baabab
baababa
baababaa
baababaab
baababaaba
baababaabab
baababaababa
baababaababaa
baababaababaab
baababaabaa
baababaabaab
baabaa
baabaab
baabaaba
baabaabab
baabaababa
baabaababaa
baabaababaab
baabaababaaba
baabaababaabab
baabaababaababa
baabaababaababaa
baabaababaabaa
baabaababaabaab

the longest of which is 16 notes long, which occurs twice, one the reverse of the other.

The program which explored all the possibilities is:

DECLARE SUB addOn (s$)
DIM SHARED songCt, maxLen
CLEAR , , 5000
OPEN "seqtones.txt" FOR OUTPUT AS #2

songCt = 2
PRINT #2, "a"
addOn "a"
PRINT #2, "b"
addOn "b"

PRINT songCt, maxLen

SUB addOn (s$)
IF RIGHT$(s$, 1) <> "b" THEN
s1$ = s$ + "b"
GOSUB tryIt
END IF
s1$ = s$ + "a"
GOSUB tryIt
EXIT SUB

tryIt:
good = 1
FOR i = 1 TO LEN(s1$) / 3
   rep$ = RIGHT$(s1$, i) + RIGHT$(s1$, i) + RIGHT$(s1$, i)
   ix = INSTR(s1$, rep$)
   IF ix THEN good = 0: EXIT FOR
NEXT
IF good THEN
    PRINT #2, s1$
    IF LEN(s1$) > maxLen THEN maxLen = LEN(s1$)
    songCt = songCt + 1
    addOn s1$
END IF
RETURN
END SUB

Posted by Charlie on 2004-12-14 15:12:18

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (13)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info