22
\$\begingroup\$

A number is in base-b simplified Goodstein form if it is written as

b + b + ... + b + c,   0 < c ≤ b

The simplified Goodstein sequence of a number starts with writing the number in base-1 simplified Goodstein form, then replacing all 1's with 2's and subtracting 1. Rewrite the result in base-2 simplified Goodstein form, then replace all 2's with 3's and subtract 1, etc. until you reach 0.

Your program is to take a positive integer input and output/print its Goodstein sequence and terminate. Your program should handle numbers less than 100, though it may not terminate in a reasonable amount of time.

For example, given 3 as the input, your program should output (the right side is just explanation)

1 + 1 + 1                | 3 = 1 + 1 + 1
2 + 2 + 1                | Change 1's to 2's, then subtract 1. (2 + 2 + 2 - 1 = 2 + 2 + 1)
3 + 3                    | 3 + 3 + 1 - 1 = 3 + 3
4 + 3                    | 4 + 4 - 1 = 4 + 3
5 + 2                    | 5 + 3 - 1 = 5 + 2
6 + 1                    | 6 + 2 - 1 = 6 + 1
7                        | 7 + 1 - 1 = 7
7                        | 8 - 1 = 7
6                        | Numbers are now lower than the base, so just keep subtracting 1.
5                        |
4                        |
3                        |
2                        |
1                        |
0                        | End

Spacing doesn't matter.


Winning criterion:

This is . Shortest code wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ Is it required to include the last 0? \$\endgroup\$ – KSab Oct 18 '17 at 0:00
  • 5
    \$\begingroup\$ @KSab Hm.... no, I guess not. \$\endgroup\$ – Simply Beautiful Art Oct 18 '17 at 0:01
2
\$\begingroup\$

05AB1E, 19 bytes

Å1[D'+ý,N>D>:`Ž<)0K

Could also be rearranged as >Å1[ND>:`Ž<)0KD'+ý,

Try it online!

Explanation

Å1                    # push a list of 1's the length of the input
  [                   # start a loop
   D                  # duplicate the current list
    '+ý,              # join on "+" and print
        N>D>:         # replace <current_iteration>+1 with <current_iteration>+2
             `        # flatten the list to the stack
              Ž       # break loop if the stack is empty
               <      # decrement the top number
                )     # wrap the stack in a list
                 0K   # remove zeroes
\$\endgroup\$
10
\$\begingroup\$

Python 2, 77 74 bytes

-3 bytes thanks to Lynn

n=input();b=1
while n:print"+".join(n/b*[`b`]+[`n%b`][:n%b]);n+=n/b-1;b+=1

Try it online!

Easily runs up to n = 100 (though the output is too long for tio fully show).

\$\endgroup\$
  • \$\begingroup\$ "Spacing doesn't matter", so you're fine there. \$\endgroup\$ – Simply Beautiful Art Oct 18 '17 at 0:24
  • \$\begingroup\$ Save a byte by reading input from STDIN: n=input() b=1 while n:… \$\endgroup\$ – Lynn Oct 18 '17 at 0:33
  • 1
    \$\begingroup\$ And two more with n+=n/b-1;b+=1. 74 bytes \$\endgroup\$ – Lynn Oct 18 '17 at 0:40
  • 1
    \$\begingroup\$ @SimplyBeautifulArt fixed \$\endgroup\$ – KSab Oct 18 '17 at 1:28
  • 1
    \$\begingroup\$ @SimplyBeautifulArt it apparently has to do with the while loop, you can't put a while following a ;. I would guess that this is because if line is started with a while each following statement (seperated by semicolons) is considered inside its scope of the while and the behavior would be ambiguous or at least somewhat opaque \$\endgroup\$ – KSab Oct 18 '17 at 2:31
3
\$\begingroup\$

Pyth, 29 bytes

WQ=hZj\++*]Z/QZ<]J%QZJ=+Qt/QZ

Try it here!

\$\endgroup\$
2
\$\begingroup\$

Mathematica, 123 bytes

(s=1~Table~#;i=1;While[s!={},Print@StringRiffle[ToString/@s,"+"];s=s/.i->i+1;s=Join[Most@s,{Last@s}-1]~DeleteCases~0;i++])&


Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 3, 155 bytes

n=int(input());l=[1]*(n+1);i=0
while l:
    l=[t+1 if t==i else t for t in l];l[-1]-=1;l=l[:-1] if l[-1]==0 else l;print("+".join(list(map(str,l))));i+=1

This can be reformatted into

n = int(input())
l = [0]*(n+1)
i = 0
while l:
    l = [t+1 if t==i else t for t in l]
    if l[-1] == 0:
        l = l[:-1]
    print("+".join(list(map(str,l))))
    i += 1
\$\endgroup\$
  • \$\begingroup\$ You miss the first line of 1+1+..., and note that your program is supposed to handle any positive integer input. \$\endgroup\$ – Simply Beautiful Art Oct 17 '17 at 23:45
  • 1
    \$\begingroup\$ Yes please. Also, MathJax doesn't work on this site :P \$\endgroup\$ – Simply Beautiful Art Oct 17 '17 at 23:49
  • 1
    \$\begingroup\$ For me, it appears you put a space in your golfed version instead of a +. \$\endgroup\$ – Simply Beautiful Art Oct 18 '17 at 0:24
  • 1
    \$\begingroup\$ 106 bytes \$\endgroup\$ – ovs Oct 18 '17 at 6:08
  • 1
    \$\begingroup\$ @RGS -~x has the same value as x+1, but you don't need to parenthesize it, as unary - (negation) and unary ~ (bitwise negation) do have a higher precedence than *. In your case [1]*-~n is equal to [1]*(n+1). \$\endgroup\$ – ovs Oct 18 '17 at 7:55
1
\$\begingroup\$

Javascript ES6, 121 chars

for(q=1,s=Array(+prompt()).fill(1).join`+`;s!=0;s=s.split(q).join(++q).replace(/\d+$/,x=>x-1).replace(/\+0$/,''))alert(s)

alert=s=>document.write(s+'\n')
document.write("<pre>")

for(q=1,s=Array(+prompt()).fill(1).join`+`;s!=0;s=s.split(q).join(++q).replace(/\d+$/,x=>x-1).replace(/\+0$/,''))alert(s)

\$\endgroup\$
1
\$\begingroup\$

Perl 5, 71 bytes

$,='+';for(@a=(++$")x<>;@a;--$a[-1]||pop@a){say@a;$_+=$_==$"for@a;$"++}

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.