Problem 1190. Golomb's self-describing sequence (based on Euler 341)

Created by James

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The Golomb's self-describing sequence {G(n)} is the only nondecreasing sequence of natural numbers such that n appears exactly G(n) times in the sequence. The values of G(n) for the first few n are</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>n = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 …</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>G(n) 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 …</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Write a MATLAB script that will give you G(n) when given n.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Efficiency is key here, since some of the values in the test suite will take a while to calculate.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

317 Solutions
126 Solvers

Last Solution submitted on Aug 11, 2020

Last 200 Solutions

Problem Comments

Solution Comments

Solution 246690

1 Comment

1 Comment

bainhome on 20 May 2013

This is a shamless answer,I admit...But the explicit recurrence relation is insanely slow,hope to see you guys solve this problem more efficient.

Solution 188623

3 Comments

3 Comments

Richard Zapor on 10 Jan 2013

I prefer g(end+1:end+g(gptr))=gptr; to usage of repmat. My machine to solve 1234567 takes 48msec vs 15.4 sec using repmat. repmat has a performance issue with large column replication. Unfortunately score is code size and not time.

Alfonso Nieto-Castanon on 10 Jan 2013

totally agree (not to mention the entire 'growing inside a loop' uglyness), cody style is very far from any reasonable coding standard...

James on 10 Jan 2013

That's very interesting. The time difference on my (presumably much older) version of MATLAB is much less. Your method gives me an average time of about 18.8 sec, while repmat gives me an average time of 19.5 sec.

Solution 188622

2 Comments

2 Comments

Freddy on 30 Jan 2013

May you give a short explanation on this solution?

Khaled Hamed on 30 Jan 2013

This is the asymptotic expression of nth term based on the golden ratio. See http://en.wikipedia.org/wiki/Golomb_sequence

Problem Recent Solvers126

Problem Tags

Problem 1190. Golomb's self-describing sequence (based on Euler 341)

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers126

Suggested Problems

More from this Author80

Problem Tags

Problem 1190. Golomb's self-describing sequence (based on Euler 341)

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers126

Suggested Problems

More from this Author80

Problem Tags

Players