# Question
Title: Code Golf Christmas Edition: How to print out a Christmas tree of height N
Given a number `N`, how can I print out a Christmas tree of height `N` using the least number of code characters? `N` is assumed constrained to a minimum value of `3`, and a maximum value of `30` (bounds and error checking are not necessary). `N` is given as the one and only command line argument to your program or script.

All languages appreciated, if you see a language already implemented and you can make it shorter, edit if possible - comment otherwise and hope someone cleans up the mess. Include newlines and White Spaces for clarity, but don't include them in the character count.

A Christmas tree is generated as such, with its "trunk" consisting of only a centered "\*"

N = 3:

```
   *
  ***
 *****
   *

```

N = 4:

```
    *
   ***
  *****
 *******
    *

```

N = 5:

```
     *
    ***
   *****
  *******
 *********
     *

```

N defines the height of the branches not including the one line trunk.

**Merry Christmas PPCG!**

# Answer
> 49 votes
# , 24 characters

`(,{.)(}:@|."1,.])[\'*'$~`

```
   (,{.)(}:@|."1,.])[\'*'$~5
    *
   ***
  *****
 *******
*********
    *

```

Explanation:

```
'*'$~5
*****

[\'*'$~5
*
**
***
****
*****

```

Then `}:@|."1` reverses each row and strips off the last column, and `,.` staples it to `]`.

Then `,{.` pastes the first column onto the bottom.

*Previous entries*:

29 characters, no spaces at all.

```
   ((\:i.@#),}.)"1$&'*'"0>:0,~i.3
  *
 ***
*****
  *
   ((\:i.@#),}.)"1$&'*'"0>:0,~i.11
          *
         ***
        *****
       *******
      *********
     ***********
    *************
   ***************
  *****************
 *******************
*********************
          *

```

---

```
   NB. *count from 1 to* n*, then 1 again*
   >:0,~i.3
1 2 3 1
   NB. *replicate '*'* x *times each*
   $&'*'"0>:0,~i.3
*
**
***
*
   NB. *reverse each row*
   (\:i.@#)"1$&'*'"0>:0,~i.3
  *
 **
***
  *
   NB. *strip off leading column*
   }."1$&'*'"0>:0,~i.3

*
**

   NB. *paste together*
   ((\:i.@#),}.)"1$&'*'"0>:0,~i.3
  *
 ***
*****
  *

```

# Answer
> 110 votes
# Brainfuck, 240 characters

```
              ,
             >++
            +++++
           +[-<---
          --->],[>+
         +++++++[-<-
        ----->]<<[->+
       +++++++++<]>>]<
      [->+>+>>>>>>>+<<<
     <<<<<<]>>>>++++++++
    [-<++++>]>++++++[-<++
   +++++>]+>>>++[-<+++++>]
  <<<<<<[-[>.<-]<[-<+>>+<]<
 [->+<]>>>>>[-<.>>+<]>[-<+>]
>.<<++<<<-<->]>>>>>>>-[-<<<<<
           <.>>>
           >>>]<
           <<<<.

```

Not yet done. It works, but only with single-digit numbers.

EDIT: Done! Works for interpreters using 0 as EOF. See `NOTE`s in commented source for those with -1.

EDIT again: I should note that because Brainfuck lacks a standard method for reading command line arguments, I used stdin (standard input) instead. ASCII, of course.

EDIT a third time: Oh dear, it seems I stripped `.` (output) characters when condensing the code. Fixed...

Here's the basic memory management of the main loop. I'm sure it can be heavily optimized to reduce the character count by 30 or so.

1. Temporary
2. Copy of counter
3. Counter (counts to 0)
4. Space character (decimal 32)
5. Asterisk character (decimal 42)
6. Number of asterisks on current line (1 + 2\*counter)
7. Temporary
8. New line character
9. Temporary?
10. Total number of lines (i.e. input value; stored until the very end, when printing the trunk)

Condensed version:

```
,>++++++++[-<------>],[>++++++++[-<------>]<<[->++++++++++<]>>]<[->+>+>>>>>>>+<<<<<<<<<]>>>>++++++++[-<++++>]>++++++[-<+++++++>]+>>>++[-<+++++>]<<<<<<[-[>.<-]<[-<+>>+<]<[->+<]>>>>>[-<.>>+<]>[-<+>]>.<<++<<<-<->]>>>>>>>-[-<<<<<<.>>>>>>]<<<<<.

```

And the pretty version:

```
ASCII to number
,>
++++++++[-<------>]  = 48 ('0')

Second digit (may be NULL)
,
NOTE:   Add plus sign here if your interpreter uses negative one for EOF
[ NOTE: Then add minus sign here
 >++++++++[-<------>]
 <<[->++++++++++<]>>  Add first digit by tens
]

Duplicate number
<[->+>+>>>>>>>+<<<<<<<<<]>>

Space char
>>++++++++[-<++++>]

Asterisk char
>++++++[-<+++++++>]

Star count
+

New line char
>>>++[-<+++++>]<<<

<<<

Main loop
[
Print leading spaces
-[>.<-]

Undo delete
<[-<+>>+<]
<[->+<]
>>

Print stars
>>>[-<.>>+<]

Add stars and print new line
>[-<+>]
>.<
<++

<<<

-<->
End main loop
]

Print the trunk
>>>>>>>
-[-<<<<<<.>>>>>>]
<<<<<.

Merry Christmas =)

```

# Answer
> 68 votes
# Perl, 50 chars

(1 relevant spaces)

perl: one line version:

```
print$"x($a-$_),'*'x($_*2+1),$/for 0..($a=pop)-1,0

```

and now with more whitesapce:

```
print $"  x ( $a - $_ ),             #"# Syntax Highlight Hacking Comment
      '*' x ( $_ * 2  + 1),
      $/
for 0 .. ( $a = pop ) - 1, 0;

$ perl tree.pl 3
   *
  ***
 *****
   *
$ perl tree.pl 11
           *
          ***
         *****
        *******
       *********
      ***********
     *************
    ***************
   *****************
  *******************
 *********************
           *
$

```

### Expanded Explanation for Non-Perl Users.

```
# print $Default_List_Seperator ( a space )
#     repeated ( $a - $currentloopiterationvalue ) times,
print $" x ( $a - $_ ),
#"# print '*' repeated( $currentloopiteration * 2 + 1 ) times.
  '*' x ( $_ * 2  + 1),
# print $Default_input_record_seperator ( a newline )
  $/
# repeat the above code, in a loop,
#   iterating values 0 to ( n - 1) , and then doing 0 again
for 0 .. ( $a = pop ) - 1, 0;
# prior to loop iteration, set n to the first item popped off the default list,
#   which in this context is the parameters passed on the command line.

```

# Answer
> 31 votes
### Language: Python (through shell), Char count: 64 (2 significant spaces)

```
python -c "
n=w=$1
s=1
while w:
    print' '*w+'*'*s
    s+=2
    w-=1
print' '*n+'*'"

$ sh ax6 11
           *
          ***
         *****
        *******
       *********
      ***********
     *************
    ***************
   *****************
  *******************
 *********************
           *

```

# Answer
> 27 votes
**Language: Windows Batch Script** (*shocking!*)

```
@echo off
echo Enable delayed environment variable expansion with CMD.EXE /V

rem Branches
for /l %%k in (1,1,%1) do (
set /a A=%1 - %%k
set /a B=2 * %%k - 1
set AA=
for /l %%i in (1,1,!A!) do set "AA=!AA! "
set BB=
for /l %%i in (1,1,!B!) do set BB=*!BB!
echo !AA!!BB!
)

rem Trunk
set /a A=%1 - 1
set AA=
for /l %%i in (1,1,!A!) do set "AA=!AA! "
echo !AA!*

```

# Answer
> 24 votes
### Ruby, 64 bytes

~~```
n=ARGV[0].to_i
((1..n).to_a+[1]).each{|i|puts' '*(n-i)+'*'*(2*i-1)}

```~~
```
n=$*[0].to_i
((1..n).to_a<<1).each{|i|puts' '*(n-i)+'*'*(2*i-1)}

```

Merry Christmas all!

Edit: Improvements added as suggested by Joshua Swink

# Answer
> 17 votes
### Language: C#, Char count: 120

```
static void Main(string[] a)
{
    int h = int.Parse(a[0]);

    for (int n = 1; n < h + 2; n++)
        Console.WriteLine(n <= h ?
            new String('*', n * 2 - 1).PadLeft(h + n) :
            "*".PadLeft(h + 1));
    }
}

```

Just the code, without formatting (120 characters):

```
int h=int.Parse(a[0]);for(int n=1;n<h+2;n++)Console.WriteLine(n<=h?new String('*',n*2-1).PadLeft(h+n):"*".PadLeft(h+1));

```

Version with 109 characters (just the code):

```
for(int i=1,n=int.Parse(a[0]);i<n+2;i++)Console.WriteLine(new String('*',(i*2-1)%(n*2)).PadLeft((n+(i-1)%n)));

```

Result for height = 10:

```
          *
         ***
        *****
       *******
      *********
     ***********
    *************
   ***************
  *****************
 *******************
          *

```

# Answer
> 16 votes
**python, "-c" trick... @61 chars (and one line)**

```
python -c"for i in range($1)+[0]:print' '*($1-i)+'*'*(2*i+1)"

```

# Answer
> 15 votes
### Language: dc (through shell) Char count: 83

A little bit shorter dc version:

```
dc -e '?d1rdsv[d32r[[rdPr1-d0<a]dsaxszsz]dsbx1-rd42rlbx2+r10Plv1-dsv0<c]dscxszsz32rlbx[*]p' <<<$1

```

EDIT: changed constant 10 into $1

# Answer
> 14 votes
Here's a reasonably space-efficient Haskell version, at 107 characters:

```
main=interact$(\g->unlines$map(\a->replicate(g-a)' '++replicate(a*2-1)'*')$[1..g]++[1]).(read::[Char]->Int)

```

running it:

```
$ echo 6 | runhaskell tree.hs
     *
    ***
   *****
  *******
 *********
***********
     *

```

Merry Christmas, all :)

# Answer
> 13 votes
### Language: dc (through shell), Char count: 119 (1 significant space)

Just for the obscurity of it :)

```
dc -e "$1dsnsm"'
[[ ]n]ss
[[*]n]st
[[
]n]sl
[s2s1[l2xl11-ds10<T]dsTx]sR
[lndlslRxlcdltlRxllx2+sc1-dsn0<M]sM
1sclMxlmlslRxltxllx
'

$ sh ax3 10
          *
         ***
        *****
       *******
      *********
     ***********
    *************
   ***************
  *****************
 *******************
          *

```

# Answer
> 9 votes
**Groovy** 62B

```
n=args[0]as Long;[*n..1,n].any{println' '*it+'*'*(n-~n-it*2)}

```

_

```
n = args[0] as Long
[*n..1, n].any{ println ' '*it + '*'*(n - ~n - it*2) }

```

# Answer
> 9 votes
Better C++, around 210 chars:

```
#include <iostream>
using namespace std;
ostream& ChristmasTree(ostream& os, int height) {
    for (int i = 1; i <= height; ++i) {
        os << string(height-i, ' ') << string(2*i-1, '*') << endl;
    }
    os << string(height-1, ' ') << '*' << endl;
    return os;
}

```

Minimized to 179:

```
#include <iostream>
using namespace std;ostream& xmas(ostream&o,int h){for(int i=1;i<=h;++i){o<<string(h-i,' ')<<string(2*i-1,'*')<<endl;}o<<string(h-1,' ')<<'*'<<endl;return o;}

```

# Answer
> 9 votes
Language: python, no tricks, 78 chars

```
import sys
n=int(sys.argv[1])
for i in range(n)+[0]:print' '*(n-i)+'*'*(2*i+1)

```

# Answer
> 8 votes
### Language: Java, Char count: 219

```
class T{ /* 219 characters */
  public static void main(String[] v){
    int n=new Integer(v[0]);
    String o="";
    for(int r=1;r<=n;++r){
      for(int s=n-r;s-->0;)o+=' ';
      for(int s=1;s<2*r;++s)o+='*';
      o+="%n";}
    while(n-->1)o+=' ';
    System.out.printf(o+"*%n");}}

```

For reference, I was able to shave the previous Java solution, using recursion, down to 231 chars, from the previous minimum of 269. Though a little longer, I do like this solution because `T` is truly object-oriented. You could create a little forest of randomly-sized `T` instances. Here is the latest evolution on that tack:

```
class T{ /* 231 characters */
  public static void main(String[] v){new T(new Integer(v[0]));}}
  String o="";
  T(int n){
    for(int r=1;r<=n;++r){
      x(' ',n-r);x('*',2*r-1);o+="%n";}
    x(' ',n-1);
    System.out.printf(o+"*%n");
  }
  void x(char c,int x){if(x>0){o+=c;x(c,x-1);}
 }

```

# Answer
> 8 votes
## C# using Linq:

```
    using System;
    using System.Linq;
    class Program
        {
            static void Main(string[] args)
            {
                int n = int.Parse(args[0]);
                int i=0;
                Console.Write("{0}\n{1}", string.Join("\n",
                   new int[n].Select(r => new string('*',i * 2 + 1)
                   .PadLeft(n+i++)).ToArray()),"*".PadLeft(n));
            }
       }

```

170 charcters.

```
int n=int.Parse(a[0]);int i=0;Console.Write("{0}\n{1}",string.Join("\n",Enumerable.Repeat(0,n).Select(r=>new string('*',i*2+1).PadLeft(n+i++)).ToArray()),"*".PadLeft(n));

```

# Answer
> 7 votes
Improving ΤΖΩΤΖΙΟΥ's answer. I can't comment, so here is a new post. 72 characters.

```
import sys
n=int(sys.argv[1])
for i in range(n)+[0]:
   print ("*"*(2*i+1)).center(2*n)

```

Using the "python -c" trick, 61 characters.

```
python -c "
for i in range($1)+[0]:
   print ('*'*(2*i+1)).center(2*$1)
"

```

I learned the center function and that "python -c" can accept more than one line code. Thanks, ΤΖΩΤΖΙΟΥ.

# Answer
> 7 votes
AWK, 86 characters on one line.

```
awk '{s="#";for(i=0;i<$1;i++){printf"%"$1-i"s%s\n","",s;s=s"##"}printf"%"$1"s#\n",""}'

echo "8" | awk '{s="#";for(i=0;i<$1;i++){printf"%"$1-i"s%s\n","",s;s=s"##"}printf"%"$1"s#\n",""}'
        #
       ###
      #####
     #######
    #########
   ###########
  #############
 ###############
        #

cat tree.txt
3
5

awk '{s="#";for(i=0;i<$1;i++){printf"%"$1-i"s%s\n","",s;s=s"##"}printf"%"$1"s#\n",""}' tree.txt
   #
  ###
 #####
   #
     #
    ###
   #####
  #######
 #########
     #

```

# Answer
> 7 votes
21 characters with dyalog APL.

```
m,⍨⌽0 1↓m←↑'*'\¨⍨1,⍨⍳

```

⍳ gives a vector of integers starting with 1.

1,⍨ adds a one to the end of the vector. This will be the foot of the tree.

'\*'\¨⍨ gives a vector of \*-strings with lengths given by the previous vector.

↑ transforms the vector to a matrix and adds spaces to the right.

m← stores the matrix in m.

0 1↓ drops zero rows and the first column.

⌽ reverses the matrix.

m,⍨ concatenates with m at the right side.

# Answer
> 7 votes
# Python 2, ~~54~~ ~~53~~ 52 bytes

This is shorter than @xnor's solution by 4 bytes.

```
i=n=input()
while~i:i-=1;print i%n*' '+~i%n*'**'+'*'

```

Try it online!

---

I borrowed @xnor's trick of using modulo (`i%n`) in order to print the trunk on the last line. The next part is figuring out how to print the number of stars.

```
   i   | ~i%n | *2+1 |
-------|------|------|
   5   |   0  |   1  |
   4   |   1  |   3  |
   3   |   2  |   5  |
   2   |   3  |   7  |
   1   |   4  |   9  |
   0   |   5  |  11  |
  -1   |   0  |   1  |

```

The example above illustrates the number of stars we need to print given our variable \\$i\\$. First, we 'invert' \\$i\\$ by doing `~i%n`. This gives us an increasing sequence starting from 0. Keep in mind that the way Python handles negative modulo is different from other languages like C.

# Answer
> 6 votes
**Language:PowerShell, Char count: 41 (including 1 space)**

```
1..$args[0]+1|%{" "*(30-$_)+"*"*($_*2-1)}

```

# Answer
> 5 votes
### Language: C, Char count: 133

Improvement of the C-version.

```
char s[61];

l(a,b){printf("% *.*s\n",a,b,s);}

main(int i,char**a){
  int n=atoi(a[1]);memset(s,42,61);
  for(i=0;i<n;i++)l(i+n,i*2+1);l(n,1);
}

```

Works and even takes the tree height as an argument. Needs a compiler that tolerates K&R-style code.

I feel so dirty now.. This is code is ugly.

# Answer
> 4 votes
### Language: Python, Significant char count: 90

It's ugly but it works:

```
import sys
n=int(sys.argv[1])
print"\n".join(" "*(n-r-1)+"*"*(r*2+1)for r in range(n)+[0])

```

...

```
$ python tree.py 13
            *
           ***
          *****
         *******
        *********
       ***********
      *************
     ***************
    *****************
   *******************
  *********************
 ***********************
*************************
            *

```

# Answer
> 4 votes
### Language: C, Char count: 176 (2 relevant spaces)

```
#include <stdio.h>
#define P(x,y,z) for(x=0;x++<y-1;)printf(z);
main(int c,char **v){int i,j,n=atoi(v[1]);for(i=0;i<n;i++){P(j,n-i," ")P(j,2*i+2,"*")printf("\n");}P(i,n," ")printf("*\n");}

```

# Answer
> 4 votes
Shell version, 134 characters:

```
#!/bin/sh
declare -i n=$1
s="*"
for (( i=0; i<$n; i++ )); do
    printf "%$(($n+$i))s\n" "$s"
    s+="**"
done
printf "%$(($n))s\n" "*"

```

# Answer
> 4 votes
## R (62 bytes)

I did not see R solution yet. Correct me if I missed it.

```
for(i in c(1:N,1))cat(rep(" ",N-i),rep("*",2*i-1),"\n",sep="")

```

Output:

```
> N <- 3
> for(i in c(1:N,1))cat(rep(" ",N-i),rep("*",2*i-1),"\n",sep="")
  *
 ***
*****
  *
>
> N <- 4
> for(i in c(1:N,1))cat(rep(" ",N-i),rep("*",2*i-1),"\n",sep="")
   *
  ***
 *****
*******
   *
>
> N <- 5
> for(i in c(1:N,1))cat(rep(" ",N-i),rep("*",2*i-1),"\n",sep="")
    *
   ***
  *****
 *******
*********
    *

```

# Answer
> 4 votes
## J, 24

Works akin to the accepted answer in that you include the parameter in the source code. Expressing it as a proper function would be slightly longer. Uses a different approach than the accepted answer.

```
' *'#~(>:@+:,.~#-])0,~i.

```

E.g.

```
   ' *' #~ (>:@+: ,.~ #-]) 0 ,~ i.5
    *
   ***
  *****
 *******
*********
    *

```

As a function (**27**):

```
#&' *'@(>:@+:,.~#-])@,&0@i.

```

# Answer
> 4 votes
# Jelly, 12 bytes

```
R”*ẋz⁶ṚŒBṁ‘Y

```

Try it online!

# Answer
> 3 votes
# PHP, 111 chars

(The very last char should be a newline.)

```
<?php $n=$argv[1];for($r='str_repeat';$i<$n;$i++)echo $r(' ',$n-$i).$r('*',$i*2+1)."\n";echo $r(' ',$n).'*' ?>

```

Readable version:

```
<?php

$n = $argv[1];

for ($r = 'str_repeat'; $i < $n; $i++)
    echo $r(' ', $n - $i) . $r('*' , $i * 2 + 1) . "\n";

echo $r(' ', $n) . '*'

?>

```

# Answer
> 3 votes
Java version. 189 character

```
class P
{
 static String p(int n, String s)
 {
  return --n < 1 ? s : p(n, s) + s;
 }

 public static void main(String[] a)
 {
  for (int N = new Integer(a[0]), i = -1; i++ < N;)
   System.out.println(p(N - i % N, " ") + p(i % N * 2 + 1, "*"));
 }
}

```

# Answer
> 3 votes
**C# - Recursion**

```
using System;

class A
{
    static string f(int n, int r)
    {
        return "\n".PadLeft(2 * r, '*').PadLeft(n + r)
            + (r < n ? f(n, ++r) : "*".PadLeft(n));
    }

    static void Main(string[] a)
    {
        Console.WriteLine(f(int.Parse(a[0]), 1));
    }
}

```

**177 chars** (not as short the other C# method posted, but a different way of doing it).

# Answer
> 3 votes
# Charcoal, 9 bytes

```
Ｇ↗↘←Ｎ*Ｍ↓*

```

Try it online!

## Verbose

```
Polygon(:UpRight, :DownRight, :Left, InputNumber(), "*")
Move(:Down)
Print("*")

```

Try it online!

# Answer
> 3 votes
# 05AB1E, 9 bytes

```
LĆ'*×j€û»

```

Try it online or verify all Christmas trees in the range \[3, 30\].

`€û»` can alternatively be `».º` for the same byte-count: try it online.

**9 bytes alternative:**

```
·ÅÉĆ'*×.c

```

Try it online or verify all Christmas trees in the range \[3, 30\].

**Explanation:**

```
L          # Create a list in the range [1, (implicit) input]
           #  i.e. 3 → [1,2,3]
 Ć         # Enclose; appending its own head
           #  → [1,2,3,1]
  '*×     '# For each value, repeat the "*" that many times as string
           #  → ["*","**","***","*"]
     j     # Prepend spaces to make all items of a length equal to the (implicit) input
           #  → ["  *"," **","***","  *"]
      €û   # Palindromize each string
           #  → ["  *  "," *** ","*****","  *  "]
        »  # Join the list by newlines
           #  → "  *  \n *** \n*****\n  *  "
           # (after which it is output implicitly as result)

·          # Double the (implicit) input-integer
           #  i.e. 3 → 6
 ÅÉ        # Pop and push a list of all odd numbers <= this integer
           #  → [1,3,5]
   Ć       # Enclose; appending its own head
           #  → [1,3,5,1]
    '*×   '# For each value, repeat the "*" that many times as string
           #  → ["*","***","*****","*"]
       .c  # Centralize it by adding leading spaces (which implicitly joins by newlines)
           #  → "  *\n ***\n*****\n  *"
           # (after which it is output implicitly as result)

```

# Answer
> 3 votes
# c: 151 116 115

Just giving it a whirl

```
i,j,a;main(c,v)int**v;{for(a=atoi(v[1]);i<a;i+=puts(""))for(j=0;j<a+i;)putchar(++j<a-i?32:42);printf("%*s",a,"*");}

```

Readable code:

```
i, j, a;
main(c, v) int **v; {
    for (a = atoi(v[1]); i < a; i += puts(""))
        for(j = 0; j < a + i;)
            putchar(++j < a - i ? 32 : 42);
    printf("%*s", a, "*");
}

```

Try it online!

# Code History:

```
main(int c, char **v){
    int i, j, a = atoi(v[1]);
    for (i = 1; i <= a; i++) {
        for (j = 0; j < a + i - 1; j++)
            putchar((j >= a - i) ? '*' : ' ');
        putchar('\n');
    }
    printf("%*s*\n", a - 1, "");
}

```

# Answer
> 3 votes
# Poetic, 547 bytes

```
the triangle trees
a december i loved
o,i placed a fun christmasy thing
i know i am hoping on a santa,a gift,cookie plates,or bag o dolls
i know i am choosing my toy to expect of him,Mr.Claus
i say,Mr,i think i may ask nicely
we are nice people,we are
o,under the tree i go crazy as i glance at the a-b-c puzzle we got
a thing on Xmas i am happy to be toying with
o,i found it!for a moment,i shouted thanks
a gift i am having as we enjoy a holiday feast
and now i sleep
oh,here i am,silent as i could
i quickly awaken
i then go to locate a present

```

Try it online!

Translated from a version by Daniel Cristofani, but optimized specifically for program length in Poetic (more groups of `>` than `<`, more groups of `+` than `-`, etc).

# Answer
> 3 votes
# K (oK), ~~33~~ 29 bytes

```
{(x+1)#(-x+!x)$(1+2*!x)#'"*"}

```

-4 thanks to streetser!

Try it online!

# Answer
> 3 votes
# Scala 3, char count ~~132~~ 124

```
@main def t(n:Int)={def p(i:Int,j:Int):Unit={println(" "*i+"*"*j);if(i==0)println(" "*(j/2)+"*");else p(i-1,j+2);};p(n-1,1)}

```

### Readable version

```
@main def t(n:Int) =
  def p(i:Int, j:Int):Unit =
    println(" " * i + "*" * j)
    if (i == 0) println(" " * (j / 2) + "*")
    else p(i - 1, j + 2)
  p(n - 1, 1)

```

### Results

```
scala xmastree.scala 3
  *
 ***
*****
  *

scala xmastree.scala 5
    *
   ***
  *****
 *******
*********
    *

```

# Answer
> 3 votes
# \>\<\>, 67 bytes

```
1:{:v :,2+1{1p461<
v!?:<-1o*84
\~$
>:?!v67*o1-
+:}}\0?;~ao1-::?!v{2

```

Try it online!

# Answer
> 2 votes
### Language: Erlang, Char count: 183 (2 relevant spaces)

Here is an Erlang version, ~181chars:

```
-module (x).
-export ([t/1]).

t(N) ->
 t(N,0).
t(0,N) ->
 io:format("~s~s~n",[string:copies(" ",N),"*"]);
t(H,S) ->
 io:format("~s~s~n",[string:copies(" ",H),string:copies("*",(S*2)+1)]),
 t(H-1,S+1).

```

(btw, happy Christmas to everyone!)

# Answer
> 2 votes
### Language: C, Char count: 433 (1 relevant space)

C version. Not short, not pretty, but it works.

```
#include <stdio.h>

void printLevel(int level, int width)
{
    int i;
    int count = level + (level - 1);
    int spaces = width - count;
    int lowerBound = spaces / 2;
    int upperBound = width - lowerBound;
    for (i = 0; i < width; i++) {
        if (i >= lowerBound && i < upperBound) {
            printf("*");
        } else {
            printf(" ");
        }
    }
    printf("\n");
}

void makeTree(int level)
{
    int i;
    int width = level * 2 - 1;
    for (i = 1; i <= level; i++) {
        printLevel(i, width);
    }
    printLevel(1, width);
}

int main(int argc, char **argv)
{
    int level = atoi(argv[1]);
    makeTree(level);
}

```

# Answer
> 2 votes
### Language: Nemerle+Nextem, Char count: 129 (1 relevant space)

Nemerle with Nextem:

```
type s=string;
module t {
    public Main(a : array[s]) : void {
     def t = int.Parse(a[0]);
     def x(i) { print s(' ',t-i) + s('*',i*2+1) }
     $[0..t].Iter(x);
     x(0)
    }
}

```

Char count: 128

Edit: Made it take an arg Edit2: Imperative now

# Answer
> 2 votes
### Language: Scala, Char count: 128 (1 relevant space)

My **Scala** version. I'm glad I have found the * operator for strings (String implicitly promoted to RichString).

```
  def tree(n:Int) {
    def vals(n:Int,k:Int) = ((1 to n) map { i => (k - i, (i * 2) - 1) }).toList
    for(j <- vals(n,n) ::: vals(1,n))
      println(" " * j._1 + "*" * j._2)
  }

```

# Answer
> 2 votes
Here's how I would do it in **Python**, very straightforward, only 103 characters:

```
import sys
n=int(sys.argv[1])
for i in range(n): print ('*'*(2*i+1)).center(2*n)
print '*'.center(2*n)

```

# Answer
> 2 votes
# JavaScript, 110 characters (2 relevant spaces)

```
function p(l)
{
    o=''
    for(c=0; c<=n+l; c++)
      o += c < n - l ? ' ' : '*'
    print(o)
}

n = parseInt(arguments[0])

for(l = 0; l < n; l++)
  p(l)
p(0)

```

Ran using spidermonkey. $ smjs christmas\_tree.js 4

## For Javascript Console 105

```
function p(l){o='';for(c=0;c<=n+l;)o+=c++<n-l?' ':'*';console.log(o)}n=+prompt();for(l=0;l<n;)p(l++);p(0)

```

# Answer
> 2 votes
PHP (133 relevant characters):

```
function xmastree($h) {
    for($i=0;$i<$h;++$i)
        echo str_repeat(' ',$h-$i-1).str_repeat('*',2*$i+1)."\n";
    echo str_repeat(' ',$h-1)."*\n";
}

```

# Answer
> 2 votes
**Language: C, Char count: 116**

I realized I could improve on my original design:

```
main(int c,char**v){char l[99],i=0;for(c=atoi(1[v]);i<c;printf("%*s%.*s\n",c,l,i++,l))l[i]=42;printf("%*c\n",c,42);}

```

Different approach (119 characters):

```
s[99],w,i=0;p(n){printf("%*.*s\n",w+n,n*2+1,s);}main(int c,char**v){w=atoi(v[1]);for(memset(s,42,99);i<w;p(i++));p(0);}

```

Old version (123 characters):

```
main(int c,char**v){char*l=calloc(c=atoi(v[1]),2),i=0;for(;i<c;printf("%*s%.*s\n",c,l,i++,l))l[i]=42;printf("%*c\n",c,42);}

```

(One byte can be saved by putting `char *l=...` in the `for` loop. That makes it non-standard, however (though `gcc` still accepts it).)

# Answer
> 2 votes
Common Lisp, 117 essential characters:

```
(defun x (n)
  (dotimes (v n)
    (format t "~v:@<~v{*~}~>~%"
            (1- (* 2 n))
            (1+ (* 2 v))
            '(())))
  (format t "~v:@<*~>~%" (1-(* 2 n)))

```

Are there any `format` gurus out there who know a better way to get repeating arbitrary characters?

# Answer
> 2 votes
**Language: Php, Char count: 110 (3 relevant spaces)**

\<? function x($n,$a,$t){return $n?str\_repeat(' ',$n).$a.x($n-1,"\**$a"," $t"):$t;}echo x($argv\[1\],"*\n","\*\n");

A bit of php recursion to reduce the count of chars to 110.

# Answer
> 2 votes
FreePascal:

```
program xmastree;

{$mode objfpc}{$H+}

uses
  {$IFDEF UNIX}{$IFDEF UseCThreads}
  cthreads,
  {$ENDIF}{$ENDIF}
  Classes
  { you can add units after this };

var x,y,h:integer;

{$IFDEF WINDOWS}{$R xmastree.rc}{$ENDIF}

procedure printRow(sp,st:integer);
var i:integer;
begin
    for i := 1 to sp do begin
    write(' ');
  end;
    for x := 1 to st do begin
    write('*');
  end;
    for x := 1 to sp do begin
    write(' ');
  end;
    writeln();
end;

begin
    val(ParamStr(1),h);
  for y := 1 to h do begin
    printRow(h-y,(y-1)*2+1);
  end;
  printRow(h-1,1);
end.

```

Output for xmastree.exe 9

```
        *
       ***
      *****
     *******
    *********
   ***********
  *************
 ***************
*****************
        *

```

# Answer
> 2 votes
# Windows Batch File

Windows batch files have poor support for string operations: they can concatename, extract and replace strings, but generation of arbitrary-length strings according to a certain pattern AFAIK can only be done via loops. This is how Zach Scrivena's solution works.

However, one can notice that the *N+1*-th tree line can be generated from the *N*-th line by cutting one leading space off and adding two traling asterisks, which pretty much simplifies the task. Also, the tree truck repeats the tree top so we can re-use that string to get rid of a few extra loops. So, here's my batch file that uses these two tricks (**165** characters):

```
@echo off
setlocal enableextensions enabledelayedexpansion
set s=
for /l %%i in (1,1,%1)do set s= !s!
set t=!s!*
for /l %%i in (1,1,%1)do echo !t!&set t=!t:~1!**
echo %s%*

```

Assuming that echo is already off and command extensions and delayed variable expansion are on, we can drop the first two lines and shorten the code down to **108** characters.

Usage:

```
> xmastree.bat 7 & pause
       *
      ***
     *****
    *******
   *********
  ***********
 *************
       *

```

# Answer
> 2 votes
# Haskell - 105 95 characters - 3 Relevant spaces

Improved on the other Haskell solution (https://codegolf.stackexchange.com/a/4267/7353) by 2 12 strokes.

* Updated `take x$cycle "*"` into `replicate x '*'`
* Removed unnecessary brackets

Updated version:

```
r=replicate;main=(\x->mapM_ putStrLn[r(x-l)' '++r(l+l-1)'*'|l<-[1..x]++[1]])=<<(readLn::IO Int)

```

Previous version:

```
c=cycle;main=(\x->mapM_ putStrLn[(take(x-l)$c" ")++(take(l+l-1)$c"*")|l<-[1..x]++[1]])=<<(readLn::IO Int)

```

Readable (updated) version:

```
main=(\ size->
          mapM_
               putStrLn
               [replicate (size - count) ' ' ++ replicate (count + count - 1) '*' | count <- [1..size] ++ [1]]
     ) =<< ( readLn :: IO Int )

```

Haskell is such an elegant language.

# Answer
> 2 votes
It's in **PHP**.

```
<center><?$t=$_GET[1]*2-$i=1;while($i<=$t){echo str_repeat('*',$i).'<br>';$i+=2;}echo'*'?><center>

```

Total characters(with spaces):**98** Total characters(with no spaces):**97** Bytes:**98**

# Answer
> 2 votes
**K 33**

```
q)k)f:{{(|:'x),'1_'x}x$(1+(!x),0)#'"*"}
q)f 4
"   *   "
"  ***  "
" ***** "
"*******"
"   *   "

```

# Answer
> 2 votes
## Bash: ~~126~~120

As there is no purpose, there is one:

```
for((z=$1-1;z;z--)){ printf -v s "%$((($1-z)*2-1))s" ""
printf "%$((2*$1-z))s\n" "${s// /*}";};printf "%$((1+$1))s\n" \*

```

This could be written:

```
#!/bin/bash
               #
              for\
            ((z=$1-
          1;z;z--));do
        printf -v s "%$((
     ($1-z)*2-1))s" "" #fil
   printf "%$((2*$1-z))s\n" \
 "${s// /*}";done;printf "%$((1
          +$1))s\n"\
              \*
              ##

```

### In use:

```
set -- 12
for((z=$1-1;z;z--)){ printf -v s "%$((($1-z)*2-1))s" ""
printf "%$((2*$1-z))s\n" "${s// /*}";};printf "%$((1+$1))s\n" \*
            *
           ***
          *****
         *******
        *********
       ***********
      *************
     ***************
    *****************
   *******************
  *********************
            *

```

## Or into the script:

```
./chrismas.sh 6
      *
     ***
    *****
   *******
  *********
      *

```

# Answer
> 2 votes
# Python - 104 / 94 characters

Alright, so I have two solutions here. One of them is, I guess, a bit "trickier", placing all of the code on one line, while the other solution is actually shorter.

```
import sys
c=int(sys.argv[1])
for i in range(c+2):print" "*(c-1)+"*"if i==c+1 else" "*(c-i)+"*"*(2*i-1)

```

That's the 104-char version. Who said python is always readable? It doesn't use any "tricks" though, which is a plus, I guess? If we split the if/else statement onto a seperate line like so:

```
import sys
c=int(sys.argv[1])
for i in range(c+1):print" "*(c-i)+"*"*(2*i-1)
print" "*(c-1)+"*"

```

...this is much neater and is actually a few characters shorter.

# Answer
> 2 votes
# Python-3x, 119 bytes

```
N = int(input())
print(' '*N+'\n','\n'.join(['\t'+' '*(N-i)+'*'*(i*2+1) for i in range(N)]) + '\n', ' '*(N+3)+'*'+'\n')

```

result:-

```
enter N value
3
   *
  ***
 *****
   *

 4
        *
       ***
      *****
     *******
        *

9
             *
            ***
           *****
          *******
         *********
        ***********
       *************
      ***************
     *****************
             *

```

# Answer
> 2 votes
## JavaScript (ES6), 58 bytes

```
f=(n,s=`*
`,l)=>n?(k=' '.repeat(--n)+s)+f(n,'**'+s,l||k):l

```

### Demo

```
f=(n,s=`*
`,l)=>n?(k=' '.repeat(--n)+s)+f(n,'**'+s,l||k):l

console.log(f(7))
```

# Answer
> 2 votes
# Python 2 - 62 Bytes:

```
i,x=input()*2,1
exec"print('*'*(x%i)).center(i);x+=2;"*(i/2+1)

```

Multiplying the input by two saves a byte because of the need for extra brackets.
There may be a way to further golf the operations.

# Answer
> 2 votes
# Python 2, 56 bytes

```
i=n=input()
exec"i=~-i%n;print' '*i+'*'*(n*2-i+~i);"*-~n

```

Try it online!

# Answer
> 2 votes
# Perl 6, 39 bytes

```
{say " "x$^a-$_,\*x$_*2-1 for 1...$a,1}

```

Try it online!

It's one of those questions, where it's easier to just print the lines in the code block.

### Explanation:

```
{say " "x$^a-$_,\*x$_*2-1 for 1...$a,1}
{                                     }   # Anonymous code block
                          for 1...$a,1    # Loop over 1 to n and 1 again
 say                                      # Print
     " "x$^a-$_                           # Leading spaces
               ,\*x$_*2-1                 # And then the amount of asterisks

```

# Answer
> 2 votes
# 05AB1E (legacy), ~~16~~ 10 bytes

```
L·<'**Ć.c»

```

Try it online!

## Explanation:

```
L·<'**Ć.c»
L          : Create a range [1..input]
 ·<        : 2n-1 every element
   '**     : Multiply every element with "*"
      Ć    : Append the first element to the end
       .c  : Centralize elements
         » : Print out with newlines

```

# Previous solution:

```
µ¾·>'**¼})Ć.c»

```

Try it online!

## Explanation:

```
µ¾·>'**I¾-ú¼})Ć»
 ¾·>'**I¾-ú      : Create the row with padding and push to stack
           ¼     : Increment the counter
µ           }    : Loop until the counter reaches the input
             )   : Enclose stack to a list
              Ć  : Append the head to the end
               » : Print out the stack with newlines

```

# Answer
> 2 votes
**Intel 4004 machine code**, 59 bytes

This 4-bit chip was the first commercial microprocessor, introduced in 1971. Multiplication and division were performed in software, and the accumulator could not be copied to one of the 16 registers except by swapping values.

```
40 33 50 0F A0 F8 B0 A0 1C 02 A1 B0 50 0F C0 24
20 A0 F8 50 2B 24 2A A1 90 F5 50 2B 24 20 A0 F8
50 2B 24 0C 53 E0 24 0D 53 E0 C0 14 32 53 E0 F8
40 2B C0 53 F0 B3 B0 A0 B1 50 02

```

The assembly code requires this python emulator for meaningful output.

```
jun start

mainloop:
    jms printline
    ld r0
    dac
    xch r0
    ld r0
    jcn an mainloop
    ld r1
    xch r0
    jms printline
    bbl 0

printline:
    fim r2 32
    ld r0
    dac
    jms printx

    fim r2 42
    ld r1
    sub r0
    ral
    jms printx

    fim r2 32
    ld r0
    dac
    jms printx

    ;carriage return
    fim r2 12
    jms $3e0
    fim r2 13
    jms $3e0

    bbl 0

printx:
    jcn az ditch
    jms $3e0
    dac
    jun printx
ditch:
    bbl 0

start:
    jms $3f0 ; input
    xch r3
    xch r0 ; running total
    ld r0
    xch r1 ; permanent total
    jms mainloop

```

Sample run:

```
$ python intel4004-emu/main.py tree.4004
8
       *
      ***
     *****
    *******
   *********
  ***********
 *************
***************
       *

```

# Answer
> 2 votes
## Batch, ~~132~~ 129 bytes

```
@!! 2>nul||cmd/q/v/c%0 %1&&exit/b
for /l %%X in (1 1 %1)do set[= ![!
set]=![!*
:*
echo%]%
set]=%]:~1%**
2>x goto:*%]:~1%&echo%[%*

```

I shamelessly copied Golfing Delayed Expansion Variables in Batch to my batch script.
Uses the bizarre ability of `GOTO :NUL` to

> allow execution of concatenated commands in the context of the caller

Edit 2020/5/1: Abused token delimiters to shorten variable names

# Answer
> 2 votes
# Vyxal `C`, 7 bytes

```
ʁd›×*×J

```

Try it Online!

# Vyxal, 13 bytes

```
ɾ×*§↵vøm:⁋₴h,

```

Try it Online!

# Answer
> 2 votes
# jq `-r`, ~~47~~ ~~41~~ 39 bytes

*-2 bytes thanks to Michael Chatiskatzi*

```
. as$n|range(.),0|" "*($n-.)+"**"*.+"*"

```

Try it online! Add 2 bytes if a leading space is not acceptable.

```
. as$n                                   Store the input number in $n
      |                                  With that number as .
       range(.)                           Numbers from 0 up to one less than .
               ,0                         and also another 0
                 |                       With each of those numbers as .
                     *($n-.)              $n minus . copies of
                  " "                     space
                            +             Concatenate
                                 *.       . copies of
                             "**"         that string
                                   +"*"   Concatenate one more asterisk

```

The `-r` flag outputs each of those strings on a separate line without wrapping it in quotes.

# Answer
> 1 votes
### Language: Python, Char count: 104

Another take at python. Note that the question requested for a script, not a function.

```
import sys
n= int(sys.argv[1])
c= lambda s: s.center(2*n)
print "\n".join(c("*"*(2*i+1)) for i in range(n)); print c("*")

$ py ax 11
          *
         ***
        *****
       *******
      *********
     ***********
    *************
   ***************
  *****************
 *******************
*********************
          *

```

# Answer
> 1 votes
First try in LUA

```
f=string.rep p=print function t(N) for i=0,N do s=f(" ",N-i) p(s..f("+",2*i-1)..s) end p(f(" ",N-1).."+"..f(" ",N-1)) end t(arg[1])

```

After selecting all of it scite tells me these are 131 chars

For clarities sake without optimizing away the \n etc:

```
f=string.rep
p=print
function t(N)
 for i=0,N do
   s=f(" ",N-i)
   p(s..f("+",2*i-1)..s)
 end
  p(f(" ",N-1).."+"..f(" ",N-1))
end
t(arg[1])

```

For the python version by ΤΖΩΤΖΙΟΥ I get shown 115 chars... Hrm, some more things to optimize

# Answer
> 1 votes
## Scala, 97 chars

This one gets n from command line.

Thanks to ΤΖΩΤΖΙΟΥ for the * operator

```
val n=args(0).toInt*2
(1.until(n,2))foreach{i=>println(" "*(n-i)+"* "*i)}
println (" "*(n-1) + "*")

```

# Answer
> 1 votes
## Language: Pike

101 Relevant characters

```
int main (int c, array a) {
    int n=(int)a[1], i,l;
    for(;i<=n; l = ++i < n ? i : 0)
        write(" " *(n-l) + "*" * (l*2+1) +"\n");
}

```

# Answer
> 1 votes
Rhino Javascript shell: 117 chars minified

```
t=['*'];
for(i=1;i<arguments[0];++i)
{
  s='*'+t[i-1]+'*';
  for(j in t)
    t[j]=' '+t[j];
  t[i]=s;
}
t[i]=t[0];print(t.join('\n'));

```

minified:

```
t=['*'];for(i=1;i<arguments[0];++i){s='*'+t[i-1]+'*';for(j in t) t[j]=' '+t[j];t[i]=s;}t[i]=t[0];print(t.join('\n'));

```

results:

```
c:\>java -jar C:\appl\Java\rhino1_7R1\js.jar c:/tmp/Xtree.js 10
         *
        ***
       *****
      *******
     *********
    ***********
   *************
  ***************
 *****************
*******************
         *

```

# Answer
> 1 votes
**Language: FoxPro 2.x for DOS (should work with Clipper too), Char count: 62**

```
para n
for h=1 to n
?spac(n-h)+repl('*',2*h-1)
endf
?spac(n-1)+'*'

```

# Answer
> 1 votes
**Language: Euphoria 147 chars (9 relevant spaces):**

```
include get.e
object
    a = command_line(),
    t = 42
a = value( a[3] )
a = a[2]
for i = 1 to a do
    puts(1, repeat( 32, a - i ) & t & 10)
    t &= "**"
end for
puts(1, repeat( 32, a - 1 ) & 42 & 10 )

```

With only relevant whitespace:

```
include get.e
object a=command_line(),t=42a=value(a[3])a=a[2]for i=1to a do puts(1,repeat(32,a-i)&t&10)t&="**"end for puts(1,repeat(32,a-1)&42&10)

```

# Answer
> 1 votes
**Excessively long version in J (97 chars)**

```
t=:3 :0
d=:0
k=:''
while.d<y
do.
k=:k,((d{((y-1)+>:i.y))$!.'*'((d{((|.i.y)))$,' ')),LF
d=:d+1
end.k,y$k
)

```

Run it this way:

```
t N

```

where N is tree height.

And Merry Xmas (a bit late).

# Answer
> 1 votes
## C# 3.0, 158 bytes

```
int n=int.Parse(a[0]);Console.WriteLine(Enumerable.Range(1,n).Concat(new int[]{1}).Select(x=>new string('*',x*2-1).PadLeft(x+n)).Aggregate((x,y)=>x+"\n"+y));

```

Ungolfed:

```
using System;
using System.Linq;
class Program
{
    static void Main(string[] a)
    {
        int n = int.Parse(a[0]);
        Console.WriteLine(Enumerable.Range(1, n).Concat(new int[] { 1 })
            .Select(x => new string('*', x * 2 - 1).PadLeft(x + n))
            .Aggregate((x, y) => x + "\n" + y));
    }
}

```

# Answer
> 1 votes
## VBScript, 106 characters

```
n = WScript.Arguments(0)
For i = 1 To n
  WScript.Echo Space(n-i+1) & String(2*i-1, "*")
Next
WScript.Echo Space(n) & "*"

```

Usage and output example:

```
> cscript christmastree.vbs 7 //nologo
       *
      ***
     *****
    *******
   *********
  ***********
 *************
       *

```

# Answer
> 1 votes
Here's a Ruby Newbie (ha! It rhymes!) with his first working solution:

Ruby 164 characters (of readable code)

```
n=gets.to_i-1
(0..n).each do |j|
    (n-j).times do
        print " "
    end
    (1+j*2).times do
        print "*"
    end
    print "\n"
end
n.times do
    print " "
end
print "*"

```

# Answer
> 1 votes
# Lua, 113 significant chars

```
s=string.rep;n=tonumber(arg[1]);r=print;for i=0,n do l=s(" ", n-i)..s("*",(n-(n-i))*2+1);r(l)end r(s(" ",n).."*")

```

# Answer
> 1 votes
# Golfscript - 27 chars

```
~:i,0+{.i\-(' '*\.)+'*'*n}%

~:i  # eval the command line arg, store in i
,0+  # create a list [0..i-1] add 0 to the end
{}%  # map this block over the list
.    # make a copy of the list element
i\-  # subtract the list element from i
(    # decrease by one more
' '* # multiply the result by ' '
\    # swap, so the list element is back on top of stack
.)+  # duplicate, add one, add the two numbers together
'*'* # multiply the result by '*'
n    # put a newline here

```

# Answer
> 1 votes
# C++, 188 bytes

```
#include<iostream>
using namespace std;
#define s string
int main(int a,char**c){int h=atoi(c[1]);for(int i=0;i<h;i++){cout<<s(h-i,' ')<<s(i*2+1,'*')<<endl;}cout<<s(h,' ')<<'*'<<endl;}

```

Ungolfed:

```
#include<iostream>

using namespace std;

int main(int a,char**c)
{
    int h = atoi(c[1]);
    for(int i=0; i<h; i++)
    {
        cout << string(h-i, ' ') << string(i*2+1, '*') << endl;
    }
    cout << string(h, ' ') << '*' << endl;
}

```

# Answer
> 1 votes
# Q, 54

```
{-1(-:)[((x+(!)x),x)]$(((&)((!)(2*x))mod 2),1)#\:"*";}

```

example:

```
q){-1(-:)[((x+(!)x),x)]$(((&)((!)(2*x))mod 2),1)#\:"*";} 10
         *
        ***
       *****
      *******
     *********
    ***********
   *************
  ***************
 *****************
*******************
         *

```

# Answer
> 1 votes
This is my first experience with code golf. So advices are welcome :)

**C: 170 chars**:

```
int main(){
    int n,m=1,x;
    scanf("%d",&n);x=2*n-1;
    for(;m<x*n+n+2;m++)
        printf("%c",m==x*n|m==x*n+n+1?42:m==x*n+1?10:m>x*n?32:!(m%(2*n-1))?10:!(m%x<n-m/x)&m%x<m/x+n+1?42:32);
}

```

# Answer
> 1 votes
I did not see a solution using `R`. The code below may not be efficient, but it seems to work (170 characters with spaces if all code placed on one line):

```
for(i in 1:4){ cat( paste( paste(rep(' ', (3-(i-1))), collapse=''),
                           paste(rep('*', (2*i-1)),   collapse=''), collapse=''),
               sep='\n'); if(i==4) cat('    *    ', sep='\n')}

    *
   ***
  *****
 *******
    *

```

# Answer
> 1 votes
# Javascript, 89

```
i=4
c=t=""
while(i){o=c,j=(i--+1)*2-3
while(j--)o+="*"
t=o+"\n"+t
c+=" "}console.log(t+o)

```

# Javascript 81

```
o=s=''
for(a=3;a--;){l=s+=' '
for(k=a*2+1;k--;)l+='*'
o=l+'\n'+o}console.log(o+l)

```

# Answer
> 1 votes
# \>\<\>: 136 chars

This one's not going to win, but because Christmas is coming again, I thought fish needed a Christmas tree too! (pun intended)

```
1-:&1$>:> :1(?!v~$:> :1(?!vv
        ^-1o" "<   ^-1o"*"<>~2+$1-:0(?!v~~&ao>" "o1-v
      ^                              oa<;o"*"^!?(1: <

```

It can be run as follows with the standard interpreter:

```
./fish.py christmas.fish -v 5

```

... for N=5. (If the file is called `christmas.fish` :P) In this way, one prepopulates the stack with the value `5`. This is the closest I could get to a command-line argument.

# Answer
> 1 votes
# Scala, 73 chars

```
val n=args(0).toInt
(1 to n):+1 foreach(i=>println(" "*(n-i)+"*"*(2*i-1)))

```

run as

```
golf.scala 10

```

# Answer
> 1 votes
# Dart, 174 characters

```
main(p){var x=-1,r='',a=int.parse(p[0]),b=a,f=(x,y,[z='']){var s='';while(x-->0)s+=y;return s+z;};while(a-->0){x+=2;r+=f(a,' ')+f(x,'*','\n');}print('$r${f(b-1,' ','*')}');}

```

# Answer
> 1 votes
# R, 94 chars

Christmas is over, but anyway:

```
t=function(N){
  f=function(i)cat(rep(" ",N-i),rep("*",2*i-3),"\n",sep="")
  lapply(2:N,FUN=f);f(2)
}

```

For trees of height 2 or more:

```
> t(2)  > t(3)  > t(5)
*        *         *
*       ***       ***
         *       *****
                *******
                   *

```

# Answer
> 1 votes
# Japt `-R`, 11 bytes

```
ÇÑÄ î*Ãp* û

```

Try it

```
Ç               :Map the range [0,input)
 Ñ              :  Multiply by 2
  Ä             :  Add 1
    î*          :  Repeat * that many times
      Ã         :End map
       p*       :Push a *
          û     :Centre pad each element with spaces to the length of the longest
                :Implicitly join with newlines

```

# Answer
> 1 votes
# Japt, 11 bytes

```
õ_ç* êÃp* û

```

Try it online!

# Answer
> 1 votes
# APL(NARS), 37 chars, 74 bytes

```
{⊃⍵{(' '⍴⍨⍺-⍵),'*'⍴⍨1+⍵×2}¨0,⍨0,⍳⍵-1}

```

test:

```
  h←{⊃⍵{(' '⍴⍨⍺-⍵),'*'⍴⍨1+⍵×2}¨0,⍨0,⍳⍵-1}
  h 5
     *
    ***
   *****
  *******
 *********
     *
  h 1
 *
 *
  h 2
  *
 ***
  *
  h 3
   *
  ***
 *****
   *

```

Ot: It seems that your sys for know if i'am a human not work good in this chellphone (so I write this because possible this step is not taken)

# Answer
> 1 votes
# Lua, ~~100~~ 99 bytes

```
p,r,n=io.write,('').rep,arg[1]for i=0,n do p(r(' ',n-i+1),r('*',i*2+1),'\n')end p(r(' ',n+1),'*\n')

```

Try it online!

Another Lua version, a little shorter.

# Answer
> 1 votes
# PHP, 79 bytes

```
while($argn)echo$r[]=str_pad("
",1+$argn--).str_pad("",++$n*2-1,"*");echo$r[0];

```

Run as pipe with `-nR` or try it online.

# Answer
> 1 votes
# Python3,81 bytes

```
n=int(input());
for j in range(n):
 print(' '*(n-j)+'*'*(2*j+1))
print(' '*n+'*')

```

try it online

# Answer
> 1 votes
# Zsh, ~~77~~ 64 bytes

Since all these old questions are now open, I think the *oldest* q. on codegolf.se needs a `zsh` answer!
Try it Online!

```
s=*;for ((;i<$1;))printf %$[$1+i++]s\\n $s&&s+=**
printf %$1s \*

```

<sub>Hat-tip to Alastair from Boxing Day 2008</sub>
<sub>NB: Putting the **printf** stuff in a function is no advantage...</sub>
<sub>NB2: ~~original for 77 bytes~~.. saved 12 bytes by eliminating quotes, braces, trailing newline</sub>

# Answer
> 1 votes
## Wren, 91 bytes

```
Fn.new{|n|
for(i in 0...n)System.print(" "*(n-i)+"*"*(2*i+1))
System.print(" "*n+"*")
}

```

Try it online!

# Answer
> 1 votes
# Keg, ~~42~~ ~~38~~ ~~32~~ 23 bytes

```
:&1ɧ1⑷:⑻$-⑬*$⑵;`*`*⑸(
'

```

Try it online!

*-9 bytes due to generating odd numbers inside of the map*

## Answer History

### 32 Bytes

```
¿&1(⑻|:2+)1^⑷:;½ℤ⑻$-⑬*^`*`*⑸(,
,

```

Try it online!

*-6 bytes due to using a mapping approach*

### 38 Bytes

```
:&®l1(©l|⑬©l*,:`*`*,
,2+©l;®l)&⑬*,`*`,

```

*-4 bytes due to  operator (space string)*

<sub>Funny story: I *almost* said this was 40 bytes before I realised that I forgot how to count.</sub>

Try it online!

I might as well place up the Keg Christmas tree for the year seeing as how it's almost December!

## Explained

```
:&®l    #Store the amount of lines in variable l and the register
1   #Push the number of stars per row
(©l|    #Repeat variable l times
    ⑬©l*,   #Print that amount of spaces
    :`*`*,  #Print that amount of stars

    ,   #Print a literal newline
    2+  #Increment the number of stars
    ©l;®l   #Update the amount of spaces to print
)
&⑬*,`*`,    #Print the bottom row

```

# Answer
> 1 votes
# Charcoal, 12 bytes

```
Ｇ<Ｎ*‖↑¶Ｍ⊖θ←*

```

Try it online

## explanation

```
Ｇ<Ｎ*             #Draw a triangle size input N with character "*"
      ‖↑           #Mirror the triangle so it is the right way round
        ¶          #Newline
         Ｍ⊖θ←    #move left input-1
               *   #"*" character
                   #the result is implicitly printed

```

# Answer
> 1 votes
# Java, 180 chars

```
interface a{static void main(String[]a){for(int N=new Byte(a[0]),i=-1;i++<N;p('*',i%N*2),p('\n',0))p(' ',N-i%N-1);}static<T>void p(T c,int i){System.out.print(c);if(i-->0)p(c,i);}}

```

I believe this is a new record for Java for this question!

```
interface a
{
    static void main(String[]a){
        for(int N=new Byte(a[0]),i=-1;i++<N;p('*',i%N*2),p('\n',0))p(' ',N-i%N-1);
    }
    static<T>void p(T c,int i){
        System.out.print(c);
        if(i-->0)p(c,i);
    }
}

```

This program uses a recursive method to get rid of unnecessary for loops and print calls. Everything in main is run in one for loop.

# Answer
> 1 votes
# Pip, 18 bytes

```
@PPZsXa-_.'*X_M\,a

```

Try it online!

I don't know how pip recognizes this lambda, but it somehow does.

-3 from DLosc.

## Explanation

```
YPPZsXa-_.'*X_M\,ay@0 a → input
              M\,a    map inclusive range of 0 - a, loop var '_'
    sXa-_             repeat space (input - _) times
         .'*X_        repeat * _ times
         .            join them:
  PZ                  palindromize the result: ' ***' → ' ***** '
YP                    print each item of the array with newline
                      and assign the array to variable y
                  y@0 return first element of y (always a single *)
                      implicitly print it

```

`@y` cannot be used here, since it changes `\,a` in the first statement.

# Answer
> 1 votes
# MAWP, 45 bytes

```
=M@![![32;1-]`M[42;1-]`M2+=M10;1-]`[32;1-]42;

```

Try it!

Takes a while for N bigger than 10

# Answer
> 1 votes
# Rockstar, 107 bytes

```
listen to N
X's0
while N-X
let X be+1
let Y be N-X
let Z be X*2-1
say " "*Y+"*"*Z

let N be-1
say " "*N+"*"

```

Try it here (Code will need to be pasted in)

# Answer
> 1 votes
# sed 4.2.2, 62 bytes, `-r` flag

```
s/0\B/ /g
:
H
s/ (0+)/0\10/
//b
:a
s/0(0+)0/ \1/
ta
H
x
y/0/*/

```

Takes input in unary (e.g. `3` is `000`), allowed as per meta consensus.

Try it online!

With comments:

```
#Replace all zeroes except the last by a space
s/0\B/ /g
#Unnamed branch label
:
#Append to hold buffer
H
#Put zeroes around a stretch of zeroes
s/ (0+)/0\10/
#Jump to unnamed label if there are any spaces left
//b
#Create a label a, and recursively remove initial/final zeroes
:a
s/0(0+)0/ \1/
ta
#Append to hold buffer
H
#Exchange hold/pattern buffers
x
#Replace 0s with asterisks
y/0/*/

```

# Answer
> 1 votes
# Ruby 2.7, 50 bytes

```
->h{t=(0...h).map{" "*(h-_1)+?**(_1*2+1)};t<<t[0]}

```

Try it online!

TIO uses an older version of Ruby, whereas in Ruby 2.7, we've numbered parameters, which saves a byte.

# Answer
> 1 votes
# Clojure, 214 bytes

```
(defn p[n](let[c(map #(inc(* % 2))(range n))l(map #(apply str %)(partition 2(interleave(map #(apply str(repeat(/ % 2)" "))(reverse c))(map #(apply str(repeat % "*"))c))))](doseq[a l](println a))(println(first l))))

```

Try it online!

Ungolfed:

```
(defn print-xmas-tree-of-height [n]
  (let [asterisk-counts       (map #(inc (* % 2)) (range n))
        asterisk-strings      (map #(apply str (repeat % "*")) asterisk-counts)
        leading-spaces        (map #(apply str (repeat (/ % 2) " ")) (reverse asterisk-counts))
        lines                 (map #(apply str %) (partition 2 (interleave leading-spaces asterisk-strings)))
        ]
    (doseq [aLine  lines]
      (println aLine))
    (println (first lines))))

```

# Answer
> 1 votes
# Raku, ~~50~~ ~~48~~ 46 bytes

(45 characters, but » is 2 bytes)

```
{(|^$^n,0)».&{printf "%{$n+$_}s
",\*x$_*2+1}}

```

Try it online!

Original 50-byte version:

```
-> \n{(|^n,0)».&{printf "%{n+$_}s
",'*'x 2*$_+1}}

```

48-byte version:

```
-> \n{(|^n,0)».&{printf "%{n+$_}s
",\*x$_*2+1}}

```

# Answer
> 0 votes
**Language: Erlang, Char count: 151**

A little bit shorter Erlang version:

```
-module(x).
-export([t/1]).
t(N)->[H|_]=T=t(N,1),io:format([T,H]).
t(0,_)->[];t(N,M)->[[d(N,32),d(M,42),10]|t(N-1,M+2)].
d(N,C)->lists:duplicate(N,C).

```

When should run with command line argument

```
-module(x).
-export([t/1]).
t([N])->[H|_]=T=t(list_to_integer(N),1),io:format([T,H]),init:stop().
t(0,_)->[];t(N,M)->[[d(N,32),d(M,42),10]|t(N-1,M+2)].
d(N,C)->lists:duplicate(N,C).

```

Invocation:

```
$ erl -noshell -noinput -run x t 11
           *
          ***
         *****
        *******
       *********
      ***********
     *************
    ***************
   *****************
  *******************
 *********************
           *

```

# Answer
> 0 votes
# GolfScript, 34 characters

Another GolfScript entry:

```
~:x,-1%[x(]+{." "*x@- 2*("*"*n.},;

```

Explanation:

```
~:x                   #read input, store into x
,                     #create array [0,1,2,...,x-1]
-1%                   #reverse it
[x(]+                 #append x-1 to the array
{." "*x@- 2*("*"*n.}, #map each element in array to this block, outputs each line
;                     #remove results of map from stack

```

The block does:

```
{.                    #duplicate value given by map (stack is now: i i)
" "*                  #push " ", times it by i (stack now: i "   ")
x                     #push x, stack is: (i "   " x), and bring i
@                     #bring i to the front (stack is: "   " x i)
- 2*(                 #pop x,i, push ((x-i)*2-1)
"*"*                  #print that many *'s
n.}                   #print newline, duplicate it so the map doesn't kill it

```

# Answer
> 0 votes
## JavaScript, 137 bytes

```
function k(a){var b="";for(i=0;i<a;i++){for(j=0;j<a*2;j++)b+=j>a-2-i
&&j<a+i?"*":" ";b+="\n"}for(i=0;i<a*2;i++)b+=i==a-1?"*":" ";return b}

```

Test case (formatting disorder is due to the first `"` marking a string):

```
k(3)

"  *
 ***
*****
  *   "

```

# Answer
> 0 votes
# Python 2, 119 116

This one generates the tree on one line:

```
import sys
h=int(sys.argv[1])
print '\n'.join([" "*(h-i)+"*"*(i*2-1) for i in range(h,0,-1)][::-1]+[" "*(h-1)+"*"])

```

It's too bad you have to import the `sys` module in Python before being able to read `argv`.

Being used from Command Prompt:

```
C:\Users\User4\Desktop>treeprint.py 6
     *
    ***
   *****
  *******
 *********
***********
     *

```

I have a Linux box but it can't connect to the Internet and only has Python 2.4, in case you're wondering why I'm using Windows.

# Answer
> 0 votes
# SOGL V0.12, ~~11~~ 10 bytes

```
ƨ*αak} *¹╚

```

Try it Here!

Explanation:

```
     }      implicitly started loop, repeated input times
ƨ*          push "**"
  α         append that to the variable A, here defaulted to an empty string
   a        load the variable A
    k       remove the first characters
       *    push "*"
        ¹   wrap in an array
         ╚  center horizontally

```

# Answer
> 0 votes
# Excel VBA, 72 Bytes

Anonymous VBE immediate window function that takes input from range `[A1]` and outputs to the VBE immediate window

```
For i=1To[A1]:[B1]=i:?Spc([A1]-i)[Rept("*",2*B1-1)]:Next:?Spc([A1-1])"*"

```

# Answer
> 0 votes
# Python 3, 83 bytes

```
f=lambda n:'\n'.join([' '*(n-1-i)+'*'*(i*2+1)for i in range(n)])+'\n'+' '*(n-1)+'*'

```

# Answer
> 0 votes
# JavaScript, ~~90~~ 89 bytes

```
f=(l,n=1,s="")=>l+1?s+=f(l-1,n+2,l?`*`.repeat(n).padStart(l+n)+`
`:"*".padStart(n/2+1)):s

```

Try it online!

---

Alternative:

```
f=(l,n=1)=>l+1&&f(l-1,n+2,console.log(l?"*".repeat(n).padStart(l+n):"*".padStart(n/2+1)))

```

Try it online!

# Answer
> 0 votes
# x86 machine code, ~~42~~ 40 bytes

Same limitation as in previous x86 answer (N \< 10) applies. It may be lifted by replacing the first four lines with the following six (+6 bytes):

```
start:
    mov si, 82h
    lodsw
    xchg al, ah
    and ax, 0F0Fh
    aad

```

Assembly source code:

```
start:
    mov si, 82h
    lodsb
    aaa
    xchg ax, cx
    mov dx, 0A2Ah
    mov di, dx
    push cx
_loop:
    push cx
    rep stosb
    xchg ax, dx
    mov cx, bx
    rep stosb
    stosw
    inc bx
    inc bx
    pop cx
    xchg ax, dx
    loop _loop
    pop cx
    rep stosb
    xchg ax, dx
    stosw
    xchg ax, dx
    mov ax, 0924h
    stosb
    int 21h
    ret

```

# Answer
> 0 votes
**SmileBASIC, 55 Bytes**

Takes input from variable 'N'

```
FOR I=1TO N?" "*(N-I);"*"*(1+(I-1)*2)NEXT?" "*(N-1);"*"

```

I think it may be possible to shorten line 2 or 3 in the breakdown below

```
FOR I=1TO N                                                Iterate values of 'I' from 1 to N (One for each layer of branches)
           ?" "*(N-I)                                      Display spaces to offset asterisks, which begins at N-1 spaces long and end at 0 spaces long
                     ;"*"*(1+(I-1)*2)                      Display Asterisks
                                     NEXT                  End loop
                                         ?" "*(N-1);"*"    Display trunk

```

# Answer
> 0 votes
## SAS, ~~70~~ 87 bytes

87 bytes. With a pop window for `N` input.

```
data;
window _ n;
display _;
do i=1to n;
s=repeat('*',i*2-2);
put@(n-i+1)s;
end;
put@n'*';
run;

```

70 bytes. Imperfect, need to assign to `N` handly.

```
data;
n=9;
do i=1to n;
s=repeat('*',i*2-2);
put@(n-i+1)s;
end;
put@n'*';
run;

```

The result is

```
        *
       ***
      *****
     *******
    *********
   ***********
  *************
 ***************
*****************
        *

```

---
Tags: code-golf, ascii-art
---


title: Sum on a Fenwick Tree

text:
# Question
Title: Sum on a Fenwick Tree
## Background Information: What is a Fenwick Tree?

With a normal array, it costs \\$O(1)\\$ to access and modify an element, but \\$O(n)\\$ to sum \\$n\\$ elements. Working with a prefix sum array (an array where the \\$i\\$th value represents the sum of the first \\$i\\$ values in the underlying data), access and summation are \\$O(1)\\$, but modification is \\$O(n)\\$. Thus, if you want to do a large amount of both, you will need a different data structure.

A Fenwick Tree is one such data structure that can solve this problem. The following diagram will help with the understanding:

Don't worry too much about the "tree" part of it. This looks like a flat array but it does represent a tree (and probably not in the sense the image makes it look like) - if you're curious about the tree part, I would recommend checking out the Wikipedia page, but it's a bit much for me to explain here.

This image shows what each value in the FT represents. For example, the 12th element of the FT is the sum of the 9th to 12th elements. The 8th element of the FT is the sum of the first 8. The 16th is the sum of all 16 values.

Note that the \\$N\\$th value represents the sum of the \\$k+1\\$th value to the \\$N\\$th value, where \\$k\\$ is the number you get when you flip the least significant bit of \\$N\\$ (the rightmost bit that is turned on). For example, 12 is `1100` in binary, so removing its LSB gives `1000`, which is 8.

Now, the above logic lets us get both our summation (and by extension, access) and modification operations to \\$O(\log N)\\$, which is individually worse than both normal and prefix-sum arrays, but combined, is a more efficient data structure if you need to do both operations a lot.

**To sum the first \\$N\\$ elements**, we start with `FT[N]`. This gives us the sum from \\$k+1\\$ to \\$N\\$. Thus, the sum of the first \\$N\\$ elements is `FT[N]` plus the sum of the first \\$k\\$ elements. We get \\$k\\$ by subtracting the least significant bit from \\$N\\$. Eventually, we reach a number like 8, and subtracting the LSB gives 0, so we stop at 0.

**The next part is about modifying a FT. This isn't required for this challenge, so feel free to skip it, but it's cool if you're interested.**

**To modify the \\$N\\$th element** (as in increasing it by a certain value) we start by modifying `FT[N]`, which clearly needs to be updated. The next value to be updated is actually very simple to find.

Observing the diagram, if we modify 12, note that we don't want to modify 13, 14, or 15. This is because they don't contain the 12th element in their summation range. We know this because by removing the LSB of any of those numbers repeatedly, we will eventually get 12. Thus, we want the first number that doesn't contain the non-trailing-zero-digits of 12 as a prefix. In this case, 12 is `1100`, so we need a number that doesn't look like `11__`.

The smallest number satisfying this condition is obtained by *adding* the LSB. Adding any smaller value would just fill in the trailing zeroes of the original number; adding the LSB changes the bit in the position of the LSB from a 1 to a 0, which gives the smallest number that doesn't share the prefix.

Therefore, if we want to update element 9, we first update 9, then the LSB of 9 is 1, so we update 9+1=10. Then, the LSB of 10 is 2, so we update 10+2=12. Then, the LSB of 12 is 4, so we update 12+4=16. Then, we would update 32, but that value is now out of range, so we stop here.

The following pseudocode shows implementations of the modify and sum operations on a FT iteratively.

```
func modify(index, change) # index points to the value in the represented array that you are modifying (1-indexed); change is the amount by which you are increasing that value
    while index <= len(fenwick_tree)
        fenwick_tree[index] += change
        index += least_significant_bit(index)

func sum(count) # sum(n) sums the first n elements of the represented array
    total = 0
    while index > 0
        total += fenwick_tree[index]
        index -= least_significant_bit(index)

least_significant_bit(x) := x & -x

```

# Challenge

Given the Fenwick tree for an array `a` and an integer `n`, return the sum of the first `n` values of `a`; that is, implement the `sum` function given as an example.

# Reference Implementation

A reference implementation in Python for both the `make_tree` and `sum` functions is provided here.

# Test Cases

These test cases are given 1-indexed, but you can accept a leading 0 to 0-index it if you would like. You may also request a trailing 0 to be included (though adding a trailing 0 should not break any solutions that do not request this).

```
[6, 6, 3, 20, 8, 12, 9, 24, 8, 12], 6 -> 32
[6, 4, 3, 36, 1, 8, 3, 16, 5, 4], 3 -> 7
[2, 10, 1, 4, 4, 2, 0, 32, 1, 14], 4 -> 4
[7, 8, 4, 36, 9, 0, 0, 8, 1, 4], 5 -> 45
[3, 0, 7, 12, 4, 18, 6, 64, 6, 14], 6 -> 30
[3, 4, 3, 28, 5, 6, 8, 40, 1, 8], 9 -> 41
[4, 8, 8, 4, 0, 18, 7, 64, 0, 12], 7 -> 29
[9, 0, 6, 16, 8, 14, 5, 64, 3, 18], 0 -> 0
[3, 14, 7, 12, 2, 6, 5, 0, 7, 18], 2 -> 14

```

# Rules

* Standard Loopholes Apply
* This is , so the shortest answer in bytes in each language will be considered the winner of its language. No answer will be marked as accepted.
* You may take the two inputs in any order and the list in any reasonable format.
* You may assume that the integers in the tree are all non-negative.
* No input validation - the index will be non-negative and at most the length of the Fenwick tree
* You may assume that all values (in the list, as the index, and the output) will be at most \\$2^{32}-1\\$

Happy Golfing!

# Answer
# Jelly, 6 bytes

```
&’$ƬịS

```

A dyadic Link that accepts \\$N\\$ on the left and the Fenwick Tree (using the trailing `0` option) on the right and yields the prefix sum.

**Try it online!** Or see the test-suite.

### How?

```
&’$ƬịS - Link: N, FT
   Ƭ   - start with k=N and collect up while distinct applying:
  $    -   last two links as a monad - f(k):
 ’     -     decrement (k)
&      -     (k) bitwise AND (k-1)
    ị  - index into (FT)
     S - sum

```
> 11 votes

# Answer
# JavaScript (ES6), 24 bytes

Expects `(array)(n)`, using the 1-indexed format.

```
a=>g=n=>n&&g(n&--n)+a[n]

```

Try it online!

### Commented

```
a =>         // outer function taking the array a[]
g = n =>     // inner recursive function taking n
  n &&       // stop if n = 0
  g(n & --n) // otherwise: do a recursive call where n AND n - 1 is passed,
             // which clears the LSB (e.g. 0b110 & 0b101 -> 0b100)
  + a[n]     // add a[n] to the final sum (where n was decremented above)

```
> 10 votes

# Answer
# , 18 15 bytes

```
+/@:{~#:#]\&.#:

```

Try it online!

-3 thanks to Jonathan Allan for pointing out that I could take the lists with an extra 0 in front

Consider index 6:

* `]\&.#:` Prefixes "under" conversion to binary. Since 6 is `1 1 0`, its prefixes, including 0 fill on the right, are:

```
1 0 0
1 1 0
1 1 0

```

And after "under" converts back to decimal we get:

```
4 6 6

```
* `#:#` Filter by the binary number:

```
1 1 0 # 4 6 6
  becomes:
4 6

```
* `+/@:{~` Select `4 6` from the list we're given and sum.
> 8 votes

# Answer
# Vyxal, ~~41~~ ~~22~~ 9 bytes

```
≬:‹⋏↔Ṫ‹İ∑

```

Try it Online!

-13 bytes thanks to Razetime.
> 7 votes

# Answer
# x64 (Windows), 13 bytes

```
31 c0
03 04 8a
c4 e2 70 f3 c9
75 f6
c3

```

In assembly:

```
    xor eax, eax
_sumloop:
    add eax, [rdx + rcx*4]
    blsr ecx, ecx
    jnz _sumloop
    ret

```

Takes the address of the FT in `rdx` and the index in `ecx`. The FT must have a zero stored as its zeroth element, to ensure that passing zero as index returns zero (it doesn't affect anything else, the only way in which the zeroth entry is used is if the index is zero to begin with, otherwise when it becomes zero the loop stops).

blsr directly implements "reset lowest set bit", and sets the zero flag according to the result, which we can then branch on.

Fun facts:

* `blsr` weighs in at a gigantic 5 bytes, which does not save space compared to a `lea \ and` pair .. but there is more to it. In any case `blsr` seemed like more fun. The fun thing is, in order to use `lea \ and`, we'd need an extra register, and on Windows we'd be forced to either pick a non-volatile register (adding size for save/restore) or one of the "numbered registers" (which would cost two extra REX prefixes to encode). However, switching to the SysV x64 calling convention would work around that, since it uses `rdi` and `rsi` for the first two parameters and that frees up `rdx` or `rcx` as a scratch register.
* `loop` (with its built-in `dec rcx`) seemed useful, but isn't, since we need the value from before the decrement as well and recreating it cancels the size benefit that `loop` might have had.
* can be adapted at no addition cost to deal with an FT with over 232 entries, but adapting it to deal with results of 232 are greater would cost an extra byte (`REX.W` on the `add`, the `xor` can stay the same). Adapting the `lea \ and` version for giant FTs would cost additional `REX.W` bytes, but for `blsr` the `W` bit is already present in the VEX-prefix so it doesn't cost extra space.
> 6 votes

# Answer
# Husk, 8 bytes

```
ΣM!U¡Sn←

```

Try it online!

There may be a way to shorten with  here. Not sure how, though.

## Explanation

```
ΣM!hU¡Sn←
     ¡    infinite list using n:
      S    Self
       n   bitwise AND with
        ←  its decrement
    U     keep all unique results
   h      remove last
 M!       map left(indices) to indexes in right(fenwick tree)
Σ         sum

```
> 5 votes

# Answer
# Python 3, ~~36~~ 34 bytes

Saved 2 bytes thanks to the man himself Arnauld!!!

```
f=lambda a,n:n and a[n]+f(a,n&~-n)

```

Try it online!

Inputs Fenwick Tree \\$a\\$ (with a leading \\$0\\$) and \\$1\\$-indexed \\$n\\$.
Returns the sum to \\$n^{\text{th}}\\$ element.
> 4 votes

# Answer
# Java, ~~49~~ ~~47~~ 35 bytes

```
a->n->{for(;n>0;n&=n-1)a[0]+=a[n];}

```

Expects array with leading zero and sets the first element of the input array to the sum.

Try it online!
> 4 votes

# Answer
# Stax, 8 bytes

```
ü→,¿(≡Y▓

```

Run and debug it

Takes inputs with a leading 0 for 0-indexing.

## Explanation

```
{cvIgi@|+
{   gi    generate values from n, till invariant:
 c         copy
  v        decrement
   I       bitwise AND
      @    get elements at those indexes in a
       |+  sum

```
> 4 votes

# Answer
# Ruby, 31 bytes

```
f=->a,n{n>0?f[a,n&n-=1]+a[n]:0}

```

Try it online!
> 4 votes

# Answer
# C (gcc), ~~31~~ ~~38~~ 36 bytes

Added 7 bytes to fix a problem kindly pointed out by Nick Kennedy and Arnauld.

```
f(a,n)int*a;{n=n?f(a,n--&n)+a[n]:0;}

```

Try it online!

Inputs a pointer \\$a\\$ to the Fenwick Tree and a \\$1\\$-based \\$n\\$.
Returns the sum to \\$n^{\text{th}}\\$ element.
> 3 votes

# Answer
# Haskell, 48 bytes

```
import Data.Bits
a!n|n<1=0|y<-n-1=a!!n+a!(n.&.y)

```

Try it online!

The relevant function is `(!)`, which takes the Fenwick tree `a` as a list of integers with a leading 0 and `n` as a 0-indexed integer.

Haskell is probably the only language which needs an import to perform bitwise operations.
> 3 votes

# Answer
# , 49 bytes

```
f=function(a,n)"if"(n,f(a,bitwAnd(n,n-1))+a[n],0)

```

Try it online!

The same approach as @Arnauld's answer.
> 3 votes

# Answer
# MMIX, ~~40~~32 bytes (~~10~~8 instrs)

Assumes array of octas, preceded by 0 octa, which first argument points to.

(jxd)

```
00000000: e302 0000 3b01 0103 8eff 0001 2202 02ff  ẉ£¡¡;¢¢¤⁾”¡¢"££”
00000010: 27ff 0101 c801 01ff 5b01 fffc f803 0000  '”¢¢Ṁ¢¢”[¢”‘ẏ¤¡¡

```

```
sfen    SET  $2,0           // s = 0
        SLU  $1,$1,3
0H      LDOU $255,$0,$1
        ADDU $2,$2,$255     // loop: s += a[n]
        SUBU $255,$1,$1
        AND  $1,$1,$255     // n &= n - 1
        PBNZ $1,0B          // if(n) goto loop
        POP  3,0            // return s

```

---

Old version:

Assumes the tree is an array of octas.

(jxd)

```
00000000: 27020008 e3000000 3b010103 42010006  '£¡®ẉ¡¡¡;¢¢¤B¢¡©
00000010: 8fff0102 220000ff 27ff0101 c80101ff  Ɓ”¢£"¡¡”'”¢¢Ṁ¢¢”
00000020: 5b00fffc f8010000                    [¡”‘ẏ¢¡¡

```

```
sfen    SUBU $2,$0,8        // a = arr - 1
        SET  $0,0           // s = 0
        SLU  $1,$1,3
        BZ   $1,1F          // if(!n) goto end
0H      LDOU $255,$1,$2
        ADDU $0,$0,$255     // loop: s += a[n]
        SUBU $255,$1,$1
        AND  $1,$1,$255     // n &= n - 1
        PBNZ $1,0B          // if(!n) goto loop
1H      POP   1,0           // end: return s

```
> 2 votes

# Answer
# PowerShell, 61 bytes

```
function f($a,$n){for(;$n-gt0;$n=$n-band$n-1){$r+=$a[$n]};$r}

```

Try it online!
> 2 votes

# Answer
# Japt, 11 bytes

Port of Arnauld's solution so be sure to +1 them.

```
©ßU&´U +UgV

```

Try it
> 2 votes

# Answer
# Charcoal, ~~19~~ 17 bytes

```
ＩΣＥ⮌↨η²∧ι§θ＆η±Ｘ²κ

```

Try it online! Link is to verbose version of code. 0-indexed. Explanation: Turns out to work somewhat like Jonah's J answer, but having to use bit twiddling instead of that handy zero-filled prefixes function.

```
     η              Input integer `n`
    ↨ ²             Converted to base 2
   ⮌                Reversed
  Ｅ                 Map over digits
        ι           Current digit
       ∧            Logical And
          θ         Input array `a`
         §          Indexed by
            η       Input integer `n`
           ＆        Bitwise And
               ²    Literal `2`
              Ｘ     Raised to power
                κ   Current index
             ±      Negated
 Σ                  Take the sum
Ｉ                   Cast to string
                    Implicitly print

```
> 2 votes

# Answer
# , 40 bytes

```
function(a,n)sum(a,-a[n%%2^(0:n)-n])*!!n

```

Try it online!

Non-recursive approach: the unique values of `n-n%%2^(0:n)` give the indices that we need to sum.

We could use `sum(a[unique(n-n%%2^(0:n))])` for 41 bytes.

However, since negative indices in  specify elements to *exclude*, they're effectively used uniquely already, so we can subtract the sum of the elements of `a` that we *don't* want (`a[n%%2^(0:n)-n]`) from the sum of `a` to get the same answer saving one byte.
This unfortunately fails when `n` equals zero, so we need to multiply the result by zero in this case (or by 1 otherwise), hence the ugly `*!!n` at the end.
> 1 votes

# Answer
# 05AB1E, 9 bytes

```
Dλ£D<&}èO

```

Try it online or verify all test cases.

### 05AB1E (legacy), 9 bytes

```
bη0ζζCÙèO

```

Port of *@Jonah*'s J answer, so make sure to upvote him as well!

Try it online or verify all test cases.

Both take the inputs in the order \\$n,a\\$, and are 0-based with the additional leading `0` in \\$a\\$.

**Explanation:**

```
 λ        # Start a recursive environment,
D £       # to output the first (implicit) input amount of values
D         # Starting with a(0) = the first (implicit) input
          # Where every following a(n) is calculated as:
          #  (implicitly push the previous term a(n-1))
   D      #  Duplicate this a(n-1)
    <     #  Decrease the copy by 1
     &    #  Bitwise-AND the a(n-1) and a(n-1)-1 together
 }        # After the recursive environment:
  è       # 0-based index each value into the second (implicit) input-list
   O      # And sum those together
          # (which is output implicitly as result)

```

```
b         # Convert the (implicit) input-integer to a binary-string
 η        # Get the prefixes of this string
  0ζζ     # Pad each with trailing 0s until the list of strings is rectangular-shaped:
   ζ      #  Zip/transpose; swapping rows/columns,
  0       #  using a "0" as filler for unequal length rows
    ζ     #  Then zip/transpose back
     C    # Convert each string back to an integer
      Ù   # Uniquify it
       è  # 0-based index each value into the second (implicit) input-list
        O # And sum those together
          # (which is output implicitly as result)

```

Note: the legacy version didn't had the recursive environment `λ` yet, so the first program only works in the new version of 05AB1E. Also, zip/transpose doesn't work with a list of strings in the new version, so the second program only works in the legacy version of 05AB1E - and would require an additional `S` (split to characters/digits) and `J` (join together) for the new version of 05AB1E: `bSη0ζζJCÙèO` \- try it online.
> 0 votes

---
Tags: code-golf, math, array
---


title: Numbers with similar powers

text:
# Question
Title: Numbers with similar powers
Given an integer ***p \> 1***, find the smallest integer ***q \> p*** such that the list of exponents in the prime factorization of ***q*** is the same of that of ***p***, no matter the order or the value of the prime factors.

## Examples

The prime factorization of ***p = 20*** is ***22 x 51***. The smallest integer greater than ***p*** with identical exponents in its prime factorization is ***q = 28 = 22 x 71***.

The prime factorization of ***p = 2500*** is ***22 x 54***. The smallest integer greater than ***p*** with identical exponents in its prime factorization is ***q = 2704 = 24 x 132***.

## Rules

* The input is guaranteed to be an integer greater than 1.
* This is , so the shortest answer in bytes wins.

## Test cases

```
Input | Output
------+-------
2     | 3
20    | 28
103   | 107
256   | 6561
768   | 1280
2500  | 2704
4494  | 4510
46552 | 46584
75600 | 105840

```

# Answer
> 10 votes
# Husk, 10 bytes

```
§ḟ¤≡ȯÖLgp→

```

Try it online!

### Explantion

```
§ḟ       →     Find the first number starting from the input + 1 such that...
        p        The prime factorisation
       g         with equal elements grouped together
    ȯÖL          and sorted by length of groups
  ¤≡             has the same shape as the above applied to the input.

```

# Answer
> 6 votes
# Mathematica, 61 bytes

```
(f[x_]:=Sort[Last/@FactorInteger@x];s=#;While[f@++s!=f@#];s)&

```

Try it online!

*-4 bytes from @Misha Lavrov*

# Answer
> 5 votes
# Jelly, ~~15~~ 14 bytes

1 byte thanks to Erik the Outgolfer.

```
ÆEḟ0Ṣ
,Ç€Eð2#Ṫ

```

Try it online!

# Answer
> 5 votes
# Pyth, 15 bytes

```
fqFmShMrPd8,QTh

```

**Try it here!** or **Verify all the test cases.**

## How does this work?

```
fqFmShMrPd8,QTh   ~ Full program. Q = first input.

f             h   ~ First input where the condition is truthy over [Q+1, Q+2, ...]
           ,QT    ~ The two element list [Q, current value (T)].
   m              ~ Map over ^ with d.
       Pd         ~ The prime factorization of d.
      r  8        ~ Run-Length encode ^.
    hM            ~ Get the first element of each.
 qF               ~ Check if the values are equal.
                  ~ Output implicitly.

```

---

## Alternatives

Another 15-byter:

```
LShMrPb8fqyQyTh

```

And a couple of (longer) alternatives:

```
fqFmSlM.gkPd,QTh
LSlM.gkPbfqyQyTh
LS/LPb{PbfqyQyTh
f!-FmlM.gkPd,QTh

```

# Answer
> 5 votes
# Python 2, ~~176~~ ~~179~~ ~~171~~ ~~170~~ 169 bytes

* Added three bytes as the question changed from *set of exponents* to *list of exponents*; `set(f)` was changed to `sorted(f)`.
* Saved eight bytes thanks to ovs; golfing the if / else block down to multiplication.
* Saved a byte; golfed `(n!=r)` to `(n>r)`.
* Saved a byte; golfed `while N>1` to `while~-N`.

```
N=input();n=-~N
def F(N):
 r,f=0,[]
 while~-N:
	for n in range(2,-~N):
	 if N%n<1:f+=[1]*(n>r);f[-1]+=n==r;r=n;N/=n;break
 return sorted(f)
while F(N)!=F(n):n+=1
print n

```

Try it online!

# Answer
> 5 votes
# Brachylog, 13 bytes

```
<.;?{ḋḅlᵐ}ᵐ=∧

```

Try it online!

It's been a long time since I posted an answer…

### Explanation

```
<.               Input < Output
 .;?             The list [Output, Input]
    {    }ᵐ      Map on [Output, Input]:
     ḋ             Prime decomposition
      ḅ            Group into sublists of consecutive equal elements
       lᵐ          Take the length of each sublist
           =∧    The result of the map must be the same for the Output and the Input

```

# Answer
> 3 votes
# Haskell, 107 bytes

```
import Data.List
import Data.Numbers.Primes
p=sort.map(1<$).group.primeFactors
f x=until((==p x).p)(+1)$x+1

```

Try it online! Usage example: `f 2500` yields `2704`.

Thanks to nimi for pointing out a flaw and saving a bunch of bytes.

---

### Without `primeFactors` build-in (117 bytes)

```
import Data.List
1%n=[]
x%n|0<-mod x n=n:div x n%n|m<-n+1=x%m
p=sort.map(1<$).group.(%2)
f x=until((==p x).p)(+1)$x+1

```

Try it online!

# Answer
> 2 votes
# Python - 141 bytes

```
def s(n):
 i=1;d={}
 while n-1:
  i+=1
  if n%i<1:d[i]=d.get(i,0)+1;n/=i;i=1
 return d.values()
a=input()
j=a+1
while s(a)!=s(j):j+=1
print j

```

# Answer
> 2 votes
# 05AB1E, 15 bytes

```
XµN‚εÓ0K{}ËNI›&

```

Try it online!

**Explanation**

```
Xµ                # Loop over N in [0 ...] until 1 match is found
  N‚              # pair N with input
    ε    }        # apply to each
     Ó            # list prime exponents
      0K          # remove zeroes
        {         # sort
          Ë       # check that they are equal
              &   # and
           NI›    # that N is greater than the input

```

# Answer
> 1 votes
# Python 3 \+ Sympy, 118 bytes

```
from sympy.ntheory import*
f=lambda k:sorted(factorint(k).values())
g=lambda i,k=2:i<k and f(k)==f(i)and k or g(i,k+1)

```

Try it online!

# Answer
> 1 votes
# , 32 bytes

```
>:@]^:(1--:&(_&q:/:~@-.0:))^:_>:

```

Try it online!

Start from input + 1 `>:` and keep incrementing while the list of prime factors `_&q:` minus any zeros `-.0:`, then sorted `/:~@`, does not match `1--:`.

# Answer
> 1 votes
# Ruby, 69 bytes

```
g=->m{m.prime_division.map{_2}.sort}
->n{((n+1)..).find{g[_1]==g[n]}}

```

Attempt This Online!

# Answer
> 1 votes
# Japt, 20 bytes

Hideous! But I can't think of a better way :\

```
@[UX]Ëk ü mÊñÃre}aUÄ

```

Try it

---
Tags: code-golf, primes, permutations
---


title: Smallest Zeroless Base

text:
# Question
Title: Smallest Zeroless Base
Given a positive integer `n`, output the smallest base `b >= 2` where the representation of `n` in base `b` with no leading zeroes does not contain a `0`. You may assume that `b <= 256` for all inputs.

## Test Cases

```
1 -> 2 (1)
2 -> 3 (2)
3 -> 2 (11)
4 -> 3 (11)
5 -> 3 (12)
6 -> 4 (12)
7 -> 2 (111)
10 -> 4 (22)
17 -> 3 (122)
20 -> 6 (32)
50 -> 3 (1212)
100 -> 6 (244)
777 -> 6 (3333)
999 -> 4 (33213)
1000 -> 6 (4344)
1179360 -> 23 ([12, 9, 21, 4, 4])
232792560 -> 23 ([15, 12, 2, 20, 3, 13, 1])
2329089562800 -> 31 ([20, 3, 18, 2, 24, 9, 20, 22, 2])
69720375229712477164533808935312303556800 -> 101 ([37, 17, 10, 60, 39, 32, 21, 87, 80, 71, 82, 14, 68, 99, 95, 4, 53, 44, 10, 72, 5])
8337245403447921335829504375888192675135162254454825924977726845769444687965016467695833282339504042669808000 -> 256 ([128, 153, 236, 224, 97, 21, 177, 119, 159, 45, 133, 161, 113, 172, 138, 130, 229, 183, 58, 35, 99, 184, 186, 197, 207, 20, 183, 191, 181, 250, 130, 153, 230, 61, 136, 142, 35, 54, 199, 213, 170, 214, 139, 202, 140, 3])

```

# Answer
# Pyth, 6 bytes

```
f*FjQT

```

**Verify all the test cases.**

## How it works

```
f*FjQT  ~ Full program.

f       ~ First positive integer where the condition is truthy.
   jQT  ~ The input converted to base of the current element.
 *F     ~ Product. If the list contains 0, then it's 0, else it is strictly positive.
          0 -> Falsy; > 0 -> Truthy.
        ~ Output the result implicitly.

```

Although Pyth's `f` operates on `1, 2, 3, 4, ...` (starting at 1), Pyth treats numbers in base 1 (unary) as a bunch of zeros, so base 1 is ignored.
> 16 votes

# Answer
# C,  ~~52~~  50 bytes

```
i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;return i;}

```

Try it online!

# C (gcc),  ~~47~~  45 bytes

```
i,k;f(n){for(i=2,k=n;k;)k=k%i++?k/--i:n;n=i;}

```

Try it online!

---

*Two bytes saved thanks to @Nevay's suggestion on @Kevin Cruijssen's answer!*
> 12 votes

# Answer
# Haskell, ~~56~~ ~~52~~ 48 bytes

```
b#n=n<1||mod n b>0&&b#div n b
f n=until(#n)(+1)2

```

Try it online!

Pretty basic but can't think of any good ways to shorten it

EDIT: Thanks to Laikoni for saving me 4 bytes! Don't know why I never thought of `!!0`. I probably should've tried removing those parentheses but I have vague memories of some weird error when you try to use `||` and `&&` together. Maybe I'm confusing it with the equality operators.

EDIT 2: Thanks @Lynn for shaving another 4 bytes! Don't know how I never knew about `until` before now.
> 9 votes

# Answer
# Wolfram Language (Mathematica), 33 bytes

```
2//.i_/;DigitCount[#,i,0]>0:>i+1&

```

Try it online!
> 7 votes

# Answer
# Husk, 7 bytes

```
→V▼MBtN

```

Try it online!

### Explanation

```
→V▼MBtN
     tN    list of natural numbers starting from 2
   MB      convert the (implicit) input to each of those bases
 V▼        find the (1-based) index of the first result where the minimum digit is truthy
→          add 1 to this index

```
> 6 votes

# Answer
# Jelly, 7 bytes

```
2b@Ạ¥1#

```

Try it online!
> 5 votes

# Answer
# Python 2, 57 bytes

```
n=x=input()
b=2
while x:z=x%b<1;b+=z;x=[x/b,n][z]
print b

```

Try it online!

This is one byte shorter than a recursive function:

```
f=lambda n,b=1,x=1:b*(x<1)or f(n,b+(x%b<1),[x/b,n][x%b<1])

```
> 5 votes

# Answer
# 05AB1E, 6 bytes

-4 bytes thanks to Adnan

```
1µNвPĀ

```

Try it online!
> 3 votes

# Answer
# Husk, 9 bytes

```
←foΠ`B⁰tN

```

Try it online!

## Explanation

```
            -- input N
        tN  -- tail of [1..] == [2..]
←f(    )    -- filter with the following:
    `B⁰     --   convert N to that base
   Π        --   product (0 if it contains 0)
←           -- only keep first element

```
> 3 votes

# Answer
# Java 8, ~~61~~ ~~56~~ 54 bytes

```
n->{int b=2,t=n;for(;t>0;)t=t%b++<1?n:t/--b;return b;}

```

Try it here.

**Explanation:**

```
n->{            // Method with integer as both parameter and return-type
  int b=2,      //  Base-integer, starting at 2
      t=n;      //  Temp-integer, copy of the input
  for(;t>0;)    //  Loop as long as `t` is not 0
    t=t%b++<1?  //   If `t` is divisible by the base `b`
                //   (and increase the base `b` by 1 afterwards with `b++`)
       n        //    Set `t` to the input `n`
      :         //   Else:
       t/--b;   //    Divide `t` by the `b-1`
                //    (by decreasing the base `b` by 1 first with `--b`)
                //  End of loop (implicit / single-line body)
  return b;     //  Return the resulting base
}               // End of method

```

~~I have the feeling this can be golfed by using an arithmetic approach.~~ It indeed can, with a port of @Steadybox' C answer, and then golfed by 2 bytes thanks to *@Nevay*.

Old (**61 bytes**) answer:

```
n->{int b=1;for(;n.toString(n,++b).contains("0"););return b;}

```

Try it here.

**Explanation:**

```
n->{         // Method with Integer as both parameter and return-type
  int b=1;   //  Base-integer, starting at 1
  for(;n.toString(n,++b).contains("0"););
             //  Loop as long as the input in base-`b` does contain a 0,
             //  after we've first increased `b` by 1 before every iteration with `++b`
  return b;  //  Return the resulting base
}            // End of method

```
> 3 votes

# Answer
# APL (Dyalog), ~~20~~ 19 bytes

```
1+⍣{~0∊⍺⊥⍣¯1⊢n}≢n←⎕

```

Try it online!

As usual, thanks to @Adám for helping out in chat and getting the code to work in TIO. Also, saving 1 byte.

This is tradfn (**trad**itional **f**unctio**n**) body. To use it, you need to assign it a name (which is in TIO's header field), enclose it in s (one before the name and one in TIO's footer field), and then call it using its name. Since it uses a quad () to take the user's input, it's called as `f \n input` instead of the usual `f input`

### How?

```
1+⍣{~0∊⍺⊥⍣¯1⊢n}≢n←⎕  ⍝ Main function.
                  n←⎕ ⍝ Assigns the input to the variable n
1+⍣{           }≢     ⍝ Starting with 1, add 1 until the expression in braces is truthy
    ~0∊               ⍝ returns falsy if 0 "is in"
        ⊥             ⍝ convert
            ⊢n        ⍝ the input
         ⍣¯1          ⍝ to base
       ⍺              ⍝ left argument (which starts at 1 and increments by 1)

```

The function then returns the resulting base.
> 3 votes

# Answer
# Python 2, 57 bytes

```
n=m=input()
b=2
while m:c=m%b<1;b+=c;m=(m/b,n)[c]
print b

```

Try it online!

-1 thanks to Felipe Nardi Batista.
-2 thanks to Lynn (and now this is a dupe of her solution :D)
> 2 votes

# Answer
# Japt, 8 bytes

```
@ìX e}a2

```

Try it online!

## Explanation

```
@    }a2

```

Return the first number (`X`) to pass the function, starting at `2`

```
ìX

```

Convert the input number to an array of base-`X` digits.

```
e

```

Check if all digits are truthy.
> 2 votes

# Answer
# JavaScript (ES6), ~~43~~ ~~41~~ 37 bytes

```
n=>(g=x=>x?g(x%b++?x/--b|0:n):b)(b=1)

```

### Test cases

```
let f =

n=>(g=x=>x?g(x%b++?x/--b|0:n):b)(b=1)

console.log(f(1   )) // 2 (1)
console.log(f(2   )) // 3 (2)
console.log(f(3   )) // 2 (11)
console.log(f(4   )) // 3 (11)
console.log(f(5   )) // 3 (12)
console.log(f(6   )) // 4 (12)
console.log(f(7   )) // 2 (111)
console.log(f(10  )) // 4 (22)
console.log(f(17  )) // 3 (122)
console.log(f(20  )) // 6 (32)
console.log(f(50  )) // 3 (1212)
console.log(f(100 )) // 6 (244)
console.log(f(777 )) // 6 (3333)
console.log(f(999 )) // 4 (33213)
console.log(f(1000)) // 6 (4344)
```
> 2 votes

# Answer
# Brachylog, 11 bytes

```
;.≜ḃ₎¬∋0∧1¬

```

Try it online!

### Explanation

```
;.≜ḃ₎           The Input represented in base Output…
     ¬∋0        …contains no 0
        ∧1¬     And Output ≠ 1

```
> 2 votes

# Answer
# Proton, 40 bytes

```
x=>filter(y=>all(digits(y,x)),2..x+3)[0]

```

Try it online!
> 1 votes

# Answer
# , ~~79~~ ~~71~~ ~~66~~ ~~63~~ 65 bytes

```
function(n){while(!{T=T+1;all(n%/%T^(0:floor(log(n,T)))%%T)})T
T}

```

Try it online!

This answer is based on Giuseppe's re-arrangement in one single loop.

Saved 8 bytes thanks to JDL, and 6 bytes thanks to Giuseppe.
> 1 votes

# Answer
# MATL, ~~13~~ 12 bytes

```
`G@Q_YAA~}@Q

```

Try it online!

-1 byte thanks to Luis Mendo. This program does not handle testcases bigger than 2^53 (`flintmax`, the maximum consecutive integer representable by a floating point type), as the default datatype is `double` in MATL. However, it should be able to find any arbitrary zeroless base below that number.

```
`            % Do while
 G           %  Push input
  @ _        %  Outputs the iteration number, negate.
     YA      %  Convert input to base given by the iteration number, the negative number is to instruct MATL we want an arbitrary high base with a integer vector rather than the default character vector we know from hexadecimal
       A~    %  If they're not all ones, repeat
         }   % But if they are equal, we finally
          @  %  Push the last base
   Q       Q %  As base 1 makes no sense, to prevent MATL from errors we always increase the iteration number by one.

```
> 1 votes

# Answer
# \>\<\>, ~~56~~ ~~52~~ ~~51~~ 49 bytes

```
:2&v
1(?\:&:&:@%@,:1%-:
 v~<
l<*v?=2
&v?/:&+1
n>&

```

Try it online!

The interpreter bugs out on the last 2 testcases.
It only reads the first 16 digits of the input correct and then replaces the rest with other digits.
> 1 votes

# Answer
# Actually,  ~~12~~  11 bytes

```
╗1⌠╜¡m'0<⌡╓

```

Try it online!

Uses this consensus. Thanks to Mego for byte-saving help in chat.
> 0 votes

# Answer
# PHP, 59+1 bytes

**using builtins**, max base 36:

```
for($b=1;strpos(_.base_convert($argn,10,++$b),48););echo$b;

```

**no builtins, ~~63~~60+1 bytes**, any base:

```
for($n=$b=1;$n&&++$b;)for($n=$argn;$n%$b;$n=$n/$b|0);echo$b;

```

Run as pipe with `-nR` or try them online.
> 0 votes

# Answer
# J, 26 bytes

```
]>:@]^:(0 e.]#.inv[)^:_ 2:

```

Would love to know if this can be improved.

The main verb is a the dyadic phrase:

```
>:@]^:(0 e.]#.inv[)^:_

```

which is given the input on the left and the constant 2 on the right. That main verb phrase then uses J's Do..While construct, incrementing the right y argument as long as 0 is an element of `e.` the original argument in base y.

Try it online!
> 0 votes

# Answer
# Lua, ~~77~~ 76 bytes

```
b=2n=...N=n
while~~N>0 do
if N%b<1then
b=b+1N=n
else
N=N//b
end
end
print(b)

```

Try it online!
> 0 votes

# Answer
# Milky Way, 38 bytes

```
^^'%{255£2+>:>R&{~^?{_>:<;m_+¡}}^^^}

```

usage: `./mw base.mwg -i 3`

---

## Explanation

```
code                                 explanation                    stack layout

^^                                   clear the preinitialized stack []
  '                                  push the input                 [input]
   %{                              } for loop
     255£                             push next value from 0..254   [input, base-2]
         2+                           add 2 to the get the base     [input, base]
           >                          rotate stack right            [base, input]
            :                         duplicate ToS                 [base, input, input]
             >                        rotate stack right            [input, base, input]
              R                       push 1                        [input, base, input, 1]
               &{~             }      while ToS (=remainder) is true ...
                  ^                    pop ToS                      [input, base, number]
                   ?{         }        if ToS (=quotient) ...
                     _>:<;              modify stack                [input, base, number, base]
                           m            divmod                      [input, base, quotient, remainder]
                           _+¡         else: output ToS (0) + SoS and exit
                                ^^^   pop everything but the input.

```

I'm sure this can be shortened using a while-loop instead of a for loop, but I couldn't get it to work.
> 0 votes

# Answer
# Stacked, 23 bytes

```
{!2[1+][n\tb all]until}

```

Try it online!

This increments (`[1+]`) **J** starting from two (`2`) while the base<sub>**J**</sub> representation of the input has no zeroes (`all` and `until`).
> 0 votes

# Answer
# Perl 5, 52 + 2 (`-pa`) = 54 bytes

```
$\=1;while($_&&=$F[0]){$\++;$_=int$_/$\while$_%$\}}{

```

Try it online!
> 0 votes

# Answer
# Ruby, 41 bytes

```
->n{(2..).find{!n.digits(_1).include? 0}}

```

Attempt This Online!
> 0 votes

# Answer
# Stax, 7 bytes

```
Ç╔ü$■╖Ö

```

Run and debug it

Trivial brute force approach
> 0 votes

# Answer
# Pip, 12 bytes

```
T NyYaTD Uoo

```

Try It Online!

### Explanation

An iterative solution:

```
T NyYaTD Uoo
              a is command-line input; y is ""; o is 1 (implicit)
T             Loop until
  Ny          Min(y) is truthy:
         Uo     Increment o
     aTD        Convert a to list of digits in that base
    Y           Store that list in y
           o  After the loop, output o

```

---

Alternate solution using filter, also **12 bytes**:

```
@:NaTD_FI2,m
              a is command-line input; m is 1000 (implicit)
         2,m  Range from 2 to 999 (could be 256, but using m is shorter)
       FI     Filter, keeping elements for which this function returns truthy:
   aTD_         Convert a to list of digits in base (function argument)
  N             Get the minimum
@:            Take the first element of the filtered list

```

Try It Online!
> 0 votes

---
Tags: code-golf, number, integer, base-conversion
---