title: Shortest power set implementation

text:
# Question
Title: Shortest power set implementation
## Problem definition

Print out the powerset of a given set. For example:

```
[1, 2, 3] => [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

```

Each element is to be printed on a separate line, so the above example would be printed as:

```
[]
[1]
[2]
...
[1, 2, 3]

```

## Example code (in D, python example here):

```
import std.stdio;

string[][] powerset(string[] set) {
    if (set.length == 1) {
        return [set, []];
    }

    string[][] ret;
    foreach (item; powerset(set[1 .. $])) {
        ret ~= set[0]~item;
        ret ~= item;
    }

    return ret;
}

void main(string[] argv) {
    foreach (set; powerset(argv[1 .. $]))
        writeln(set);
}

```

## Input

Elements will be passed as arguments. For example, the example provided above would be passed to a program called `powerset` as:

```
powerset 1 2 3

```

Arguments will be alphanumeric.

## Rules

1. No libraries besides io
2. Output does not have to be ordered
3. Powerset does not have to be stored, only printed
4. Elements in the set must be delimited (e.g. `1,2,3`, `[1,2,3]` and `['1','2','3']` are acceptable, but `123` is not
    * Trailing delimiters are fine (e.g. `1,2,3, == 1,2,3`)
5. *Best* is determined based on number of bytes

The best solution will be decided no less than 10 days after the first submission.

# Answer
# Mathematica 16

**Code**

`Subsets` is native to Mathematica.

```
Column@Subsets@s

```

The code (without column) can be verified on WolframAlpha. (I had to use brackets instead of `@`; they mean the same thing.

**Usage**

```
s={1,2,3}
Column@Subsets@s

```

---

This method (55 chars) uses the approach suggested by @w0lf.

```
s #&/@Tuples[{0,1},Length@s]/.{0:>Sequence[]}//Column

```

**Breakdown**

Generate the tuples, composed of `0` and `1`'s of length `Length[s]`

```
Tuples[{0, 1}, Length@s]

```

> {{0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 1, 1}, {1, 0, 0}, {1, 0, 1}, {1, 1, 0}, {1, 1, 1}}

Multiply the original list (vector) by each tuple:

```
s # & /@ Tuples[{0, 1}, Length@s]

```

> {{0, 0, 0}, {0, 0, 3}, {0, 2, 0}, {0, 2, 3}, {1, 0, 0}, {1, 0, 3}, {1, 2, 0}, {1, 2, 3}}

Delete the `0`'s. `%` is shorthand for "the preceding output".

%/. {0 :\> Sequence\[\]}

> {{}, {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}}

Display in column:
> 16 votes

# Answer
## C, 118 115

Whilst can save approx 20 chars with simpler formatting, still not going to win in code golf terms either way.

```
x,i,f;
main(int a,char**s){
    for(;x<1<<a;x+=2,puts("[]"+f))
        for(i=f=0;++i<a;)x&1<<i?f=!!printf("%c%s","[,"[f],s[i]):0;
}

```

Testing:

```
/a.out 1 2 3
[]
[1]
[2]
[1,2]
[3]
[1,3]
[2,3]
[1,2,3]

```
> 10 votes

# Answer
### GolfScript, 22 18 characters

```
~[[]]{{+}+1$%+}@/`

```

Another attempt in GolfScript with a completely different algorithm. Input format is the same as with w0lf's answer. (online test)
> 7 votes

# Answer
## GolfScript (43 chars)

This may seem quite long, but it's the first solution to follow the spec: input is from command-line arguments, and output is newline-delimited.

```
"#{ARGV.join('
')}"n/[[]]\1/{`{1$+.p}+%}%p;

```

E.g.

```
$ golfscript.rb powset.gs 1 2 3
["1"]
["2"]
["2" "1"]
["3"]
["3" "2"]
["3" "1"]
["3" "2" "1"]
[]

```
> 5 votes

# Answer
## awk (82)

```
{for(;i<2^NF;i++){for(j=0;j<NF;j++)if(and(i,(2^j)))printf "%s ",$(j+1);print ""}}

```

assume saved in file powerset.awk, usage

```
$ echo 1 2 3 | awk -f powerset.awk

1
2
1 2
3
1 3
2 3
1 2 3

```

**ps** if your awk doesn't have and() function, replace it with `int(i/(2^j))%2` but adds two to the count.
> 4 votes

# Answer
## JavaScript, 98

Sadly, a good chunk is spent on output formatting.

```
for(n in a=eval(prompt(i=p=[[]])))
    for(j=i+1;j;)
        p[++i]=p[--j].concat(a[n]);
alert('[]'+p.join('\n'))

```

### Input

Takes a JavaScript array. (e.g. \[1,2,3\])

### Output

```
[]
1
1,2
2
2,3
1,2,3
1,3
3

```
> 3 votes

# Answer
## Python ~~70~~ 67 bytes

```
def p(a,*v):
 i=0;print v
 for n in a:i+=1;p(a[i:],n,*v)
p(input())

```

Input is taken in the same manner as for ugoren's solution. Sample I/O:

```
$ echo [1,2,3] | powerset.py
()
(1,)
(2, 1)
(3, 2, 1)
(3, 1)
(2,)
(3, 2)
(3,)

```

Try it online!
> 3 votes

# Answer
## J, 19 chars

```
   (<@#~#:@i.@(2&^)@#)

   (<@#~#:@i.@(2&^)@#) 1 2 3
┌┬─┬─┬───┬─┬───┬───┬─────┐
││3│2│2 3│1│1 3│1 2│1 2 3│
└┴─┴─┴───┴─┴───┴───┴─────┘

```

The ascii boxing in the output is called `boxing` and provides heterogen collection (for different length of arrays here).
> 3 votes

# Answer
## Golfscript 48

```
~:x,:§2\?,{[2base.,§\-[0]*\+x\]zip{~{}{;}if}%p}%

```

This program uses the binary representations of numbers from 0 to length(input) to generate powerset items.

### Input

The input format is the Golfscript array format (example: `[1 2 3]`)

### Output

The output is a collection of arrays separated by newlines, representing the power set. Example:

```
[]
[3]
[2]
[2 3]
[1]
[1 3]
[1 2]
[1 2 3]

```

### Online Test

The program can be tested online here.
> 2 votes

# Answer
# Python (74 70 chars)

```
def p(a,v):
 if a:i,*a=a;p(a,v);p(a,v+[i])
 else:print v
p(input(),[])

```

for input as `1,2,3` or `[1,2,3]`, output is:

```
[]
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]

```
> 2 votes

# Answer
## Haskell (96)

```
import Control.Monad
import System.Environment
main=getArgs>>=mapM print.filterM(\_->[False ..])

```

If importing `Control.Monad` isn't allowed, this becomes **100** characters:

```
import System.Environment
main=getArgs>>=mapM print.p
p z=case z of{[]->[[]];x:y->p y++map(x:)(p y)}

```
> 2 votes

# Answer
## Ruby, 39

```
$*.map{p *$*.combination($.)
$.+=1}
p$*

```
> 2 votes

# Answer
**Mathematica 53**

```
Column@Fold[#~Join~Table[x~Join~{#2},{x,#}]&,{{}},#]&

```
> 2 votes

# Answer
# C# 164

Man this is hard in C#!

```
void P<T>(T[]c){foreach(var d in c.Aggregate<T,IEnumerable<IEnumerable<T>>>(new[]{new T[0]},(a,b)=>a.Concat(a.Select(x=>x.Concat(new[]{b})))))Console.WriteLine(d);}

```
> 2 votes

# Answer
**Scala, 81**

```
def p[A](x:Seq[A]){x.foldLeft(Seq(Seq[A]()))((a,b)=>a++a.map(b+:_)).map(println)}

```
> 2 votes

# Answer
## APL (26)

Reads input from keyboard because there's no `argv` equivalent.

```
↑⍕¨(/∘T)¨↓⍉(M/2)⊤⍳2*M←⍴T←⎕

```

Usage:

```
      ↑⍕¨(/∘T)¨↓⍉(M/2)⊤⍳2*M←⍴T←⎕
⎕:
      1 2 3
3
2
2 3
1
1 3
1 2
1 2 3

```

Explanation:

* `T←⎕`: read input, store in `T`
* `M←⍴T`: store length of `T` in `M`
* `(M/2)⊤⍳2*M`: generate the bit patterns for `1` upto `2^M` using `M` bits.
* `↓⍉`: split the matrix so that each bit pattern is separate
* `(/∘T)¨`: for each bit pattern, select those sub-items from `T`.
* `↑⍕¨`: for output, get the string representation of each element (so that it will fill using blanks and not zeroes), and format as a matrix (so that each element is on its own line).
> 2 votes

# Answer
# JavaScript (*ES6*) 76

Partially copied from this one: https://codegolf.stackexchange.com/a/51502/21348

Using a bitmap, so it's limited to no more than 32 elements.

Run the snippet in Firefox to test.

```
f=l=>{
  for(i=0;i<1<<l.length;i++)
    console.log(l.filter(v=>[i&m,m+=m][0],m=1))
}

// TEST

// Redefine console to have output inside the page
console = { log: (...p) => O.innerHTML += p.join(' ') + '\n' }

test=()=>{
  var set = I.value.match(/[^ ,]+/g)
  O.innerHTML='';
  f(set);
}

test()
```

```
#I,#O { border: 1px solid #aaa; width: 400px; padding:2px}
```

```
Insert values, space or comma separated:<br>
<input id=I value='1 2 3'> <button onclick="test()">-></button>
<pre id=O></pre>
```
> 2 votes

# Answer
# K, 14 bytes

```
{x@&:'!(#x)#2}

```

Generate all 0/1 vectors as long as the input, gather the indices of 1s and use those to select elements from the input vector. In practice:

```
  {x@&:'!(#x)#2} 1 2 3
(!0
 ,3
 ,2
 2 3
 ,1
 1 3
 1 2
 1 2 3)

```

This is a bit liberal with the output requirements, but I think it's legal. The most questionable part is that the empty set will be represented in a type dependent form; `!0` is how K denotes an empty numeric vector:

```
  0#1 2 3      / integers
!0
  0#`a `b `c   / symbols
0#`
  0#"foobar"   / characters
""

```

## Explanation

The `(#x)#2` builds a vector of `2` as long as the input:

```
  {(#x)#2}1 2 3
2 2 2
  {(#x)#2}`k `d `b `"+"
2 2 2 2

```

When monadic `!` is applied to a vector, it is "odometer":

```
  !2 2 2
(0 0 0
 0 0 1
 0 1 0
 0 1 1
 1 0 0
 1 0 1
 1 1 0
 1 1 1)

```

Then we use "where" (`&`) on each (`'`) vector to gather its indices. The colon is necessary to disambiguate between the monadic and dyadic form of `&`:

```
  &0 0 1 0 1 1
2 4 5

  {&:'!(#x)#2} 1 2 3
(!0
 ,2
 ,1
 1 2
 ,0
 0 2
 0 1
 0 1 2)

```

If we just wanted combination vectors, we'd be done, but we need to use these as indices into the original set. Fortunately, K's indexing operator `@` can accept a complex structure of indices and will produce a result with the same shape:

```
  {x@&:'!(#x)#2} `a `c `e
(0#`
 ,`e
 ,`c
 `c `e
 ,`a
 `a `e
 `a `c
 `a `c `e)

```

Elegant, no?
> 2 votes

# Answer
## Python 2, 64 bytes

Using comma-separated input:

```
P=[[]]
for i in input():P+=[s+[i]for s in P]
for s in P:print s

```

## Pyth, 4 bytes (using builtin) or 14 bytes (without)

As noted by @Jakube in the comments, Pyth is too recent for this question. Still here's a solution using Pyth's builtin powerset operator:

```
jbyQ

```

And here's one without it:

```
jbu+Gm+d]HGQ]Y

```

You can try both solutions here and here. Here's an explanation of the second solution:

```
jb       # "\n".join(
 u       #  reduce(
  +G     #   lambda G,H: G+
   m     #    map(
    +d]H #     lambda d: d+[H],
    G    #     G),
  Q      #   input()
  ]Y     #   [[]]))

```
> 2 votes

# Answer
## brainfuck, 94 bytes

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

```

Formatted:

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

```

Expects input of the form `9,10,11` without a trailing newline, and outputs subsets in the same format, sometimes with a trailing comma. The first line printed will always be empty, signifying the empty set.

Try it online.

The basic idea is to place a bit next to each element, then repeatedly increment the binary number while printing the corresponding subset before each increment. (A bit indicates whether an element is in the subset.) A sentinel bit to the left of the array is used to terminate the program. This version actually creates an exponential number of sentinels to save some bytes; a more efficient 99-byte solution that only uses one sentinel can be found in the revision history.

Each bit is encoded as one plus its value; i.e., it can be either `1` or `2`. The tape is laid out with the bit before each element and a single zero cell between adjacent elements. The comma is included on the tape for non-final elements, so we can conveniently just print elements without doing any extra work to handle delimiters.
> 2 votes

# Answer
# Jelly, 6 bytes

```
ŒPŒṘ€Y

```

Try it online!

`ŒṘ€Y` are string formatting.
> 2 votes

# Answer
# APL (Dyalog Classic), 13 bytes

```
⍪,⊃∘.,/⎕,¨⊂⊂⍬

```

Try it online!

Output:

```
 1 2 3
 1 2
 1 3
 1
 2 3
 2
 3

```

There's a blank line at the end to represent the empty set.

Explanation:

evaluated input

`⎕,¨⊂⊂⍬` append an empty numeric list after each element

`∘.,` Cartesian product

`/` reduction (foldr)

disclose (necessary after reduction in APL)

At this point the result is an n-dimensional 2-by-...-by-2 array, where n is the length of the input.

`,` flatten into a vector

turn the vector into an upright 2n-by-1 matrix, so each subset is on a separate line
> 2 votes

# Answer
# Haskell, ~~80~~ 78 bytes

```
import System.Environment
main=getArgs>>=mapM(print.concat).mapM(\a->[[a],[]])

```

Try it online!
> 2 votes

# Answer
# Python 2, 63 bytes

```
def f(s,p=[[]]):
 for e in s:
  for u in p:p=p+[u+[e]]
 print p

```

Try it online!
> 2 votes

# Answer
# JavaScript (ES6), 68 bytes

```
a=>alert(a.reduce((a,x)=>[...a,...a.map(y=>[...y,x])],[[]]).join`
`)

```

### Demo

```
let f =

a=>alert(a.reduce((a,x)=>[...a,...a.map(y=>[...y,x])],[[]]).join`
`)

f([1,2,3])
```
> 1 votes

# Answer
# Japt `-R`, ~~5~~ 1 byte

~~Sadly, Japt's built-in for getting the powerset of an array doesn't include the empty array or this would be 1 byte.~~ It does now!

```
à

```

Try it (the empty line at the end is the empty set or you can run it with the `-Q` flag instead to visualise the sub-arrays)
> 1 votes

# Answer
# Brachylog, 4 bytes

```
⊇ᵘẉᵐ

```

Try it online!

```
  ẉ     Write on its own line
 ᵘ ᵐ    every unique
⊇       subset of the input.

```
> 1 votes

# Answer
# Zsh, 31 bytes

Accidentally cut my previous byte-count in half answering another prompt...

```
for i;a=({$i,}\ $^a)
<<<${(F)a}

```

Try it online!

Delimiter is one or more spaces, we abuse trailing delimiters extensively here.
> 1 votes

# Answer
# Pyth, 1 byte

```
y

```

Since Pyth has implicit `Q` (input variable) at the end of programs, this is basically just power set of the input. I don't think this violates any rules (although 'No libraries besides io' is a bit vague)

Try it online!
> 1 votes

# Answer
# PHP, 102 bytes

```
<?php
function p($a){
$b=[[]];foreach($a as $c)foreach($b as $d)$b[]=array_merge([$c],$d);return $b;
}

```

# Go, 118 bytes

```
package m
func p(a ...int)[][]int{b:=[][]int{{}}
for _,c:=range a{for _,d:=range b{b=append(b,append(d,c))}}
return b}

```
> 1 votes

# Answer
# Thunno 2, 3 bytes

```
ʠ¶j

```

Try it online!

#### Explanation

```
ʠ¶j  # Implicit input
ʠ    # Take the powerset
 ¶j  # Join on newlines
     # Implicit output

```
> 1 votes

# Answer
# Nekomata, 1 byte

```
S

```

Attempt This Online!

`S` finds a subset of a list.

By default, Nekomata prints all possible results separated by newlines.
> 1 votes

# Answer
## Python, 93 87 chars

Python makes formatting simple, because the required input/output matches its native format.
Only supports items which are Python literals (e.g. `1,2,'hello'`, not `1,2,hello`).
Reads standard input, not parameters.

```
f=lambda x:x and f(x[1:])+[x[:1]+a for a in f(x[1:])]or[()]
for l in f(input()):print l

```
> 0 votes

# Answer
### Ruby Array method combination (from 1.9 ) \[50 chars\]

```
0.upto(ARGV.size){|a|ARGV.combination(a){|v| p v}}

```
> 0 votes

# Answer
# Python 2, 74 bytes

```
def f(x):
    for i in reduce(lambda s,e:s+[i+[e] for i in s],x,[[]]):print i

```
> 0 votes

# Answer
## Haskell 89 chars

```
import System.Environment
main=getArgs>>=mapM print.p
p[]=[[]]
p(x:y)=(map(x:)$p y)++p y

```

Getting parameters is long :/
> 0 votes

# Answer
## R, 63

```
y=lapply(seq(v),function(x)cat(paste(combn(v,x,s=F)),sep="\n"))

```

Here, `v` represents a vector.

**Usage**:

```
v <- c(1, 2, 3)
y=lapply(seq(v),function(x)cat(paste(combn(v,x,s=F)),sep="\n"))
1
2
3
c(1, 2)
c(1, 3)
c(2, 3)
c(1, 2, 3)

```
> 0 votes

# Answer
# Mathematica, 51

More cheating:

```
Column@ReplaceList[Plus@@HoldForm/@#,x___+___->{x}]&

```

Use with `@{1,2,3}`.
> 0 votes

# Answer
## Matlab (46)

```
v=input(''),for i=1:numel(v),nchoosek(v,i),end

```

---

* the input must be of the form \[% % % ..\] where % is a number
> 0 votes

# Answer
# Perl 6, 22 bytes

```
say words.combinations

```

The built in `combinations` method will give all N-combinations of a list, ie. the powerset. Arguments provided via STDIN

```
% echo 1 2 3 | ./powerset.p6
(() (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3))

```
> 0 votes

# Answer
# Japt `-R`, 5 bytes

```
à i[]

```

Try it online!
> 0 votes

# Answer
# Common Lisp, 117 bytes

```
(labels((p(l &aux(x(car l)))(if x`(,@#1=(p(cdr l)),@(mapcar(lambda(m)(cons x m))#1#))'(()))))(mapcar'print(p(read))))

```

Input is a list of element, in output the sets are printed as lists (empty list is equal to NIL)

Try it online!

If the answer can be a function that returns the result, then:

## Common Lisp, 90 bytes

```
(defun p(l &aux(x(car l)))(if x`(,@#1=(p(cdr l)),@(mapcar(lambda(m)(cons x m))#1#))'(())))

```

Try it online!
> 0 votes

# Answer
# Coconut, 90 bytes

```
def p(l)=(fmap((+)$(l[:1]),p(l[1:])))+p(l[1:])if l else[[]]
fmap(print,p(input().split()))

```

I *think* I had something one byte shorter but I lost it after experimenting more.

Try it online!
> 0 votes

# Answer
# PHP, 78 bytes

```
for(;$i<1<<$argc;$i+=2)for(print$c=_;$argc>$c+=1;)$i&1<<$c&&print"$argv[$c],";

```

prints a comma after each element and an underscore before each subset. Run with `-nr` or try it online.
> 0 votes

# Answer
# 05AB1E, 2 bytes

```
æ»

```

Try it online.

Output is space-delimited (i.e. `1 2 3`). If you want it as actual lists (i.e. `[1, 2, 3]`), add `€¸` before the `»`:

```
æ€¸»

```

Try it online.

**Explanation:**

```
æ     # Take the powerset of the (implicit) input-list
   »  # Join the lists by newlines (and each inner list by spaces)
      # (and output the result implicitly)

 €¸   # Wrap each inner list into a list
      # (i.e. [[1],[1,2]] → [[[1]],[[1,2]]])

```
> 0 votes

# Answer
# Python 2, 58 bytes

```
S=lambda A:A and[u+[A[0]]for u in S(A[1:])]+S(A[1:])or[[]]

```

Try it online!
> 0 votes

# Answer
## PostScript, 80 bytes

```
00000000: 921a 2f6c 923e 9233 3088 0132 206c 2065  ../l.>.30..2 l e
00000010: 7870 2031 92a9 7b2f 6e92 3e92 335b 3088  xp 1..{/n.>.3[0.
00000020: 016c 2031 92a9 7b6e 2032 926a 3192 3d7b  .l 1..{n 2.j1.={
00000030: 921b 9201 9258 7d7b 9275 7d92 552f 6e20  .....X}{.u}.U/n
00000040: 6e88 ff92 0f92 337d 9248 5d3d 3d7d 9248  n.....3}.H]==}.H

```

Usage: `gsnd -c 1 2 3 -- powerset.ps` gives output

```
[]
[3]
[2]
[3 2]
[1]
[3 1]
[2 1]
[3 2 1]

```

Un-tokenized version:

```
count /l exch def
0 1 2 l exp 1 sub{
    /n exch def
    [
    0 1 l 1 sub{
        n 2 mod 1 eq{
            counttomark add index
        }{
            pop
        }ifelse
      /n n -1 bitshift def
    }for
    ] ==
}for

```
> 0 votes

---
Tags: code-golf, array, combinatorics
---


title: Recover the power from the prime power

text:
# Question
Title: Recover the power from the prime power
It seems that many people would like to have this, so it's now a sequel to this challenge!

**Definition**: a *prime power* is a natural number that can be expressed in the form pn where p is a prime and n is a natural number.

**Task**: Given a prime power pn \> 1, return the power n.

**Testcases**:

```
input output
9     2
16    4
343   3
2687  1
59049 10

```

**Scoring**: This is . Shortest answer in bytes wins.

# Answer
> 7 votes
# Python 2, 37 bytes

```
f=lambda n,i=2:i/n or(n%i<1)+f(n,i+1)

```

Try it online!

Counts factors. Apparently I wrote the same golf in 2015.

Narrowly beats out the non-recursive

**Python 2, 38 bytes**

```
lambda n:sum(n%i<1for i in range(1,n))

```

Try it online!

# Answer
> 6 votes
# 05AB1E, 2 bytes

```
Òg

```

Try it online!

# Answer
> 5 votes
# Python 3, 49 bytes

```
f=lambda n,x=2:n%x and f(n,x+1)or n/x<2or-~f(n/x)

```

Try it online!

Outputs `True` instead of 1 (as allowed by OP). Recursive function that repeatedly finds the lowest factor and then calls the function again with the next lowest power until it reaches 1. This is an extension of my answer to the previous question.

# Answer
> 5 votes
# Bash \+ GNU utilities, 22

* 2 bytes saved thanks to @H.PWiz and @Cowsquack

```
factor|tr -cd \ |wc -c

```

Try it online!

# Answer
> 5 votes
# Stax, \\$\require{cancel}\xcancel 4 3\\$ bytes

```
|f%

```

Run and debug it

Length of prime factorization.

# Answer
> 5 votes
# 22 bytes

Power `n` is the number of multiples of `p` in `p^n` when `p` is prime:

```
sum(!(b<-scan())%%2:b)

```

Try it online!

# Answer
> 5 votes
## Nibbles 5 bytes

```
,|`,$~^%@

```

This is 9 nibbles each of which is encoded in a half byte in the binary form. I think this is the shortest solution that doesn't use built in factoring.

Translation:

```
,      length
 |     filter
  `,$  0..input
  ~    not \x->
   ^   pow (so that 0 which would have been 0 from the mod isn't)
    %  mod
     @ input
     implicit $ (x)
    implicit $ (x)

```

It works by just counting the number of numbers the input divides evenly

You could run it passing in a list of numbers to process in stdin or as a command line arg. Nibbles isn't on TIO.run yet...

# Answer
> 4 votes
# dc, ~~50~~ 41 bytes

```
1si[dli1+dsi%0<X]dsXx[dli/dli<Y]sYdli<Yzp

```

Try it online!

Takes input from the top of the stack (in TIO, put the input in the header to load it onto the stack before execution). Outputs to stdout.

# Explanation

**Registers used:**

`i`: the current trial divisor, while `X` is running. Later, the divisor we've found.

`X`: the macro `dli1+dsi%0<X`, which has the effect "increment `i`, then check the modulus with the value on the stack (which will be the original input). If it's not zero, repeat".

`Y`: the macro `dli/dli<Y`, which has the effect "Add to the stack a copy of the current top of the stack, divided by `i`. Repeat until `i` is reached."

Full program:

```
1si                 Initialize i
[dli1+dsi%0<X]dsXx  Define and run X
[dli/dli<Y]sY       Define Y
dli<Y               Run Y, but only if needed (if the input wasn't just i)
z                   The stack is i^n, i^(n-1), ... ,i, so print the stack depth

```

# Answer
> 4 votes
# Pyth, 2

Count prime factors:

```
lP

```

Online test.

# Answer
> 4 votes
# face, 86 bytes

```
(%d@)\$*,c'$,io>Av"[""mN*c?*m1*mp*m%*s1"$pN1p:~+p1p%%Np?%~:=/NNp+?1?-%N1?%=p%'$i?w1'%>

```

Hooray, longer than Java!

Try it online!

I am particularly fond of the trick of using the return value of `sscanf`. Normally the return value would be discarded, but here it will always be 1, because we're always reading a single number as input. We can take advantage of this by assigning its return value to the variable `1`, saving the 2 bytes that would otherwise be required to assign `1` to 1 explicitly.

```
(%d@)

\$*,c'$,io>  ( setup - assign $ to "%d", * to a number, o to stdout )
Av"[""mN*    ( set " to input and allocate space for N for int conversion )
c?*          ( calloc ?, starting it at zero - this will be the output )
m1*          ( allocate variable "1", which gets the value 1 eventually )
mp*m%*       ( p is the prime, % will be used to store N mod p )

s1"$pN       ( scan " into N with $ as format; also assigns 1 to 1 )

1p:~         ( begin loop, starting p at 1 )
  +p1p       ( increment p )
  %%Np       ( set % to N mod p )
?%~          ( repeat if the result is nonzero, so that we reach the factor )

:=           ( another loop to repeatedly divide N by p )
  /NNp       ( divide N by p in-place )
  +?1?       ( increment the counter )
  -%N1       ( reuse % as a temp variable to store N-1 )
?%=          ( repeat while N-1 is not 0 -- i.e. break when N = 1 )

p%'$i?       ( sprintf ? into ', reusing the input format string )
w1'%>        ( write to stdout )

```

# Answer
> 4 votes
# Attache and Wolfram Language (Mathematica) polyglot, 10 bytes

```
PrimeOmega

```

Try Attache online! Try Mathematica online!

Simply a builtin for computing the number of prime factors **N** has.

## Explanation

Since **N** = **p***k*, Ω(**N**) = Ω(**p***k*) = *k*, the desired result.

# Answer
> 4 votes
# Whitespace, 141 bytes

```
[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_STDIN_as_number][T    T   T   _Retrieve][S S S T  N
_Push_1][N
S S N
_Create_Label_LOOP_1][S S S T   N
_Push_1][T  S S S _Add][S N
S _Duplicate][S T   S S T   S N
_Copy_2nd_input][S N
T   _Swap_top_two][T    S T T   _Modulo][N
T   S S N
_If_0_Jump_to_Label_BREAK_1][N
S N
N
_Jump_to_Label_LOOP_1][N
S S S N
_Create_Label_BREAK_1][S S S N
_Push_0][S T    S S T   S N
_Copy_2nd_input][N
S S T   N
_Create_Label_LOOP_2][S N
S _Duplicate_input][S S S T N
_Push_1][T  S S T   _Subtract][N
T   S S S N
_If_0_Jump_to_Label_BREAK_2][S N
T   _Swap_top_two][S S S T  N
_Push_1][T  S S S _Add][S N
T   _Swap_top_two][S T  S S T   S N
Copy_2nd_factor][T  S T S _Integer_divide][N
S N
T   N
_Jump_to_Label_LOOP_2][N
S S S S N
_Create_Label_BREAK_2][S N
N
_Discard_top][T N
S T _Print_as_number]

```

Letters `S` (space), `T` (tab), and `N` (new-line) added as highlighting only.
`[..._some_action]` added as explanation only.

Try it online (with raw spaces, tabs and new-lines only).

**Explanation in pseudo-code:**

```
Integer n = STDIN as input
Integer f = 1
Start LOOP_1:
  f = f + 1
  if(n modulo-f == 0)
    Call function BREAK_1
  Go to next iteration of LOOP_1

function BREAK_1:
  Integer r = 0
  Start LOOP_2:
    if(n == 1)
      Call function BREAK_2
    r = r + 1
    n = n integer-divided by f
    Go to next iteration of LOOP_2

function BREAK_2:
  Print r as number to STDOUT
  Program stops with an error: Exit not defined

```

**Example run: `input = 9`**

```
Command    Explanation                    Stack           Heap    STDIN   STDOUT   STDERR

SSSN       Push 0                         [0]
SNS        Duplicate top (0)              [0,0]
TNTT       Read STDIN as number           [0]             {0:9}   9
TTT        Retrieve                       [9]             {0:9}
SSSTN      Push 1                         [9,1]           {0:9}
NSSN       Create Label_LOOP_1            [9,1]           {0:9}
 SSSTN     Push 1                         [9,1,1]         {0:9}
 TSSS      Add top two (1+1)              [9,2]           {0:9}
 SNS       Duplicate top (2)              [9,2,2]         {0:9}
 STSSTSN   Copy 2nd from top              [9,2,2,9]       {0:9}
 SNT       Swap top two                   [9,2,9,2]       {0:9}
 TSTT      Modulo top two (9%2)           [9,2,1]         {0:9}
 NTSSN     If 0: Jump to Label_BREAK_1    [9,2]           {0:9}
 NSNN      Jump to Label_LOOP_1           [9,2]           {0:9}

 SSSTN     Push 1                         [9,2,1]         {0:9}
 TSSS      Add top two (2+1)              [9,3]           {0:9}
 SNS       Duplicate top (3)              [9,3,3]         {0:9}
 STSSTSN   Copy 2nd                       [9,3,3,9]       {0:9}
 SNT       Swap top two                   [9,3,9,3]       {0:9}
 TSTT      Modulo top two (9%3)           [9,3,0]         {0:9}
 NTSSN     If 0: Jump to Label_BREAK_1    [9,3]           {0:9}
NSSSN      Create Label_BREAK_1           [9,3]           {0:9}
SSSN       Push 0                         [9,3,0]         {0:9}
STSSTSN    Copy 2nd from top              [9,3,0,9]       {0:9}
NSSTN      Create Label_LOOP_2            [9,3,0,9]       {0:9}
 SNS       Duplicate top (9)              [9,3,0,9,9]     {0:9}
 SSSTN     Push 1                         [9,3,0,9,9,1]   {0:9}
 TSST      Subtract top two (9-1)         [9,3,0,9,8]     {0:9}
 NTSSSN    If 0: Jump to Label_BREAK_2    [9,3,0,9]       {0:9}
 SNT       Swap top two                   [9,3,9,0]       {0:9}
 SSSTN     Push 1                         [9,3,9,0,1]     {0:9}
 TSSS      Add top two (0+1)              [9,3,9,1]       {0:9}
 SNT       Swap top two                   [9,3,1,9]       {0:9}
 STSSTSN   Copy 2nd from top              [9,3,1,9,3]     {0:9}
 TSTS      Integer-divide top two (9/3)   [9,3,1,3]       {0:9}
 NSNTN     Jump to Label_LOOP_2           [9,3,1,3]       {0:9}

 SNS       Duplicate top (3)              [9,3,1,3,3]     {0:9}
 SSSTN     Push 1                         [9,3,1,3,3,1]   {0:9}
 TSST      Subtract top two (3-1)         [9,3,1,3,2]     {0:9}
 NTSSSN    If 0: Jump to Label_BREAK_2    [9,3,1,3]       {0:9}
 SNT       Swap top two                   [9,3,3,1]       {0:9}
 SSSTN     Push 1                         [9,3,3,1,1]     {0:9}
 TSSS      Add top two (1+1)              [9,3,3,2]       {0:9}
 SNT       Swap top two                   [9,3,2,3]       {0:9}
 STSSTSN   Copy 2nd from top              [9,3,2,3,3]     {0:9}
 TSTS      Integer-divide top two (3/3)   [9,3,2,1]       {0:9}
 NSNTN     Jump to Label_LOOP_2           [9,3,2,1]       {0:9}

 SNS       Duplicate top (1)              [9,3,2,1,1]     {0:9}
 SSSTN     Push 1                         [9,3,2,1,1,1]   {0:9}
 TSST      Subtract top two (1-1)         [9,3,2,1,0]     {0:9}
 NTSSSN    If 0: Jump to Label_BREAK_2    [9,3,2,1]       {0:9}
NSSSSN     Create Label_BREAK_2           [9,3,2,1]       {0:9}
 SNN       Discard top                    [9,3,2]         {0:9}
 TNST      Print as integer               [9,3]           {0:9}           2
                                                                                error

```

Program stops with an error: No exit found.

# Answer
> 4 votes
# Brachylog, 2 bytes

```
ḋl

```

Try it online!

### Explanation

```
ḋ        Prime decomposition
 l       Length

```

# Answer
> 4 votes
# APL (Dyalog Extended), ~~8~~ 2 bytes

```
≢⍭

```

Try it online!

finds factors,  counts how many of them there are.

# Answer
> 3 votes
# QBasic, ~~51~~ 41 bytes

```
INPUT n
FOR i=2TO n
f=f-(n/i=n\i)
NEXT
?f

```

-10 bytes by copying the approach from Darren Smith's Nibbles answer: For a prime power input, the desired output equals the number of integers between 1 (exclusive) and the input (inclusive) that evenly divide the input.

```
INPUT number
FOR testFactor = 2 TO number
  ' number is divisible by testFactor if their float division equals
  ' their int division
  isDivisible = (number / testFactor = number \ testFactor)
  ' Truthy is -1 in QBasic, so we subtract rather than add to the tally
  numFactors = numFactors - isDivisible
NEXT testFactor
PRINT numFactors

```

# Answer
> 3 votes
# Add++, 42 bytes

```
D,f,@,bUbU$^=
L,dVfbUG$XGRzGGXzÞ{f}bUbU0$:

```

Try it online!

I don't even know where to begin explaining this mess.

## Explained

```
D,f,@,bUbU$^=
D,f,@,        ; a helper function f that given a list [number, [x, y]]
      bUbU$^  ;   returns whether x ^ y
            = ;   equals number

L,dVfbUG$XGRzGGXzÞ{f}bUbU0$:
L,                            ; a lambda that
  dV                          ; places its input into the register
    fbU                       ; and gets the prime factor of the input. This is guaranteed to be a single item because the input is a prime raised to a power.
       G$X                    ; push a list of input copies of that power
          GRz                 ; and zip that with the range [1...input]
             GGX              ; also, push input copies of the input
                z             ; and zip that with our big list. I'm calling it a big list because it is what it is.
                 Þ{f}         ; filter that list based on the results of the helper function f
                     bUbU0$:  ; get the power out of the many nested lists returned.

```

# Answer
> 3 votes
# HBL, 7 bytes

*(or possibly 6.5 depending on how this meta question shakes out)*

```
+(*'?(*%.(02.

```

Try it!

### Explanation

```
+(*'?(*%.(
         (0    Inclusive range
           2    from 2
            .   to the argument
     (*        Map over each value x in that list:
       %.       Argument mod x
 (*            Map over each value in that list:
   '?           Logical negation
               The result is a list containing 1 for each number that divides
               the argument, 0 otherwise
+              Take its sum

```

# Answer
> 3 votes
# Risky, 3 bytes

```
!\?___

```

Try it online!

---

A basically built-in solution for now, working on a non-trivial version (might not be possible given Risky's heavy investment in specific operators, and generally awful control flow).

```
!      Count
 \     Prime factors
  ?    Input
   ___ (Padding)

```

# Answer
> 3 votes
# Nekomata, 1 byte

```
ƒ

```

Attempt This Online!

`ƒ` factorizes the input number, and returns a list of unique prime factors and a list of exponents.

Only the top of the stack will be printed, which is the list of exponents. Since the input is a prime power, this will be a singleton list.

# Answer
> 2 votes
# Jelly, ~~3~~ 2 bytes

```
Æḍ

```

Try it online!

# Answer
> 2 votes
# Java 8, 59 bytes

A lambda from `int` to `int`.

```
x->{int f=1,c=0;while(x%++f>0);for(;x>1;c++)x/=f;return c;}

```

Try It Online

# Answer
> 2 votes
# J, 4 bytes

```
#@q:

```

`q:` gives the list of prime factors, `#` gives the length of the list.

Try it online!

# Answer
> 2 votes
# , 37 bytes

```
length(numbers::primeFactors(scan()))

```

Try it online!

# Answer
> 2 votes
# MATL, 3 bytes

```
Yfz

```

Try it online!

### Explanation:

```
     % Implicit input: 59049
Yf   % Factorize input [3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
  z  % Number of non-zero elements: 10
     % Implicit output

```

# Answer
> 2 votes
# Vyxal `l`, 1 byte

```
ǐ

```

Try it Online!

-1 byte thx to @lyxal

Length of the prime factors, the flags are cheaty+awesome

# Answer
> 2 votes
# MS Excel, 33 bytes

An anonymous worksheet function that takes input from cell `A1` and outputs to the calling cell

```
-SUM(-(MOD(A1,SEQUENCE(A1))<1))-1

```

# Answer
> 2 votes
# Thunno 2 `L`, 1 byte

```
f

```

Try it online!

Push the prime `f`actors of the input then take the `L`ength of the list.

# Answer
> 1 votes
# Python 2, 62 bytes

```
def f(n,p=2,i=0):
	while n%p:p+=1
	while n>p**i:i+=1
	return i

```

Try it online!

Nothing fancy here.

# Answer
> 1 votes
# Japt, 3 bytes

```
k l

```

Try it online!

## Explanation:

```
k l
k     Get the prime factors of the input
  l   Return the length

```

# Answer
> 1 votes
# Actually, 2 bytes

```
ol

```

Try it online!

# Answer
> 1 votes
# Haskell, 27 bytes

```
f n=sum$(0^).mod n<$>[2..n]

```

Try it online!

Counts factors. Compare:

**Haskell, 28 bytes**

```
f n=sum[1|0<-mod n<$>[2..n]]

```

Try it online!

**Haskell, 28 bytes**

```
f n=sum[0^mod n i|i<-[2..n]]

```

Try it online!

**Haskell, 30 bytes**

```
f n=sum[1|i<-[2..n],mod n i<1]

```

Try it online!

# Answer
> 1 votes
# Octave, 18 bytes

```
@(x)nnz(factor(x))

```

Try it online!

Does what it says on the tin: Number of non-zero elements in the prime factorization of the input.

# Answer
> 1 votes
# Cjam, 5 bytes

```
rimf,

```

Try it Online!

Explanation:

```
ri      take the input and convert it to an int
  mf    factors the input
    ,   take the length of the list

```

Builtins are great!

# Answer
> 1 votes
# JavaScript (Node.js), 29 bytes

```
f=(n,k=n)=>--k&&!(n%k)+f(n,k)

```

Try it online! Note: Stack overflows for larger inputs.

# Answer
> 1 votes
# F#, 91 bytes

```
let rec d n c v=if v=n then c else d(n/v)(c+1)v
let p n=d n 1(Seq.find(fun x->n%x=0){2..n})

```

Try it online!

`p` gets the prime factor. `d` recursively divides the target value until it's equal to the prime factor and returns the count from that.

# Answer
> 1 votes
# Julia, 19 bytes

port of Xi'an's answer in R

```
n->sum(n.%(2:n).<1)

```

Try it online!

# Answer
> 1 votes
# Retina 0.8.2, 30 bytes

```
.+
$*
((?=(1+)(\2+)$)\3)+1
$#1

```

Try it online! Link includes test cases. Explanation:

```
.+
$*

```

Convert the input to unary.

```
((?=(1+)(\2+)$)\3)+1

```

Repeatedly find the largest factor of the current value. Eventually this becomes 1, which is then matched at the end outside of the loop.

```
$#1

```

Output the resulting number of factors, which for a prime power will be the power.

# Answer
> 1 votes
# Factor \+ `math.primes.factors`, 18 bytes

```
[ factors length ]

```

Try it online!

# Answer
> 1 votes
# Excel, 34 bytes

```
=SUM((MOD(A1,SEQUENCE(A1-1))=0)*1)

```

Link to Spreadsheet

Counts the factors. Works up to 2 ^ 20.

# Answer
> 1 votes
# Husk, 2 bytes

```
Lp

```

Try it online!

### Explanation

```
Lp
L  length of
 p prime factors

```

# Answer
> 1 votes
# BQN, 7 bytesSBCS

```
+´0=↕|⊢

```

Run online!

Translates directly to Dyalog APL:

```
+/0=⍳|⊢

```

Try it online!

# Answer
> 0 votes
# Gaia, 2 bytes

```
ḍl

```

Try it online!

# Answer
> 0 votes
# JavaScript (ES6), 37 bytes

```
f=(n,k=2)=>n%k?n>1&&f(n,k+1):1+f(n/k)

```

Try it online!

# Answer
> 0 votes
# Perl 6, 36 bytes

```
{round .log/log (2..*).first: $_%%*}

```

Looks for the first factor `(2..*).first: $_%%*`, then from there calculates the approximate value (logs won't get it exact) and rounds it.

Try it online!

# Answer
> 0 votes
# Pari/GP, 8 bytes

```
bigomega

```

Try it online!

> bigomega(x): number of prime divisors of x, counted with multiplicity.

---

# Pari/GP, 14 bytes

```
n->numdiv(n)-1

```

Try it online!

# Answer
> 0 votes
# Racket, 31 bytes

```
(car(cdr(perfect-power(read))))

```

Try it online!

# Answer
> 0 votes
# Perl 6, 18 bytes

```
{+grep($_%%*,^$_)}

```

Try it online!

Anonymous code block that gets a list of factors and coerces it to a number.

---
Tags: code-golf, number, arithmetic, primes
---


# Question
Title: (Cops) Fast and Golfiest Season 1: The Lord of the Strings
## Fast and Golfiest Cops Thread

Welcome to the first season of **Fast and Golfiest**, a cops-and-robbers challenge! I designed this challenge to encourage competitive coding for efficiency (fastest algorithm) to become more popular on the site.

The rules are simple. The cops must choose a problem from LeetCode, the prestigious competitive programming platform, and *independently* solve it with code that is as efficient and as short as possible. The problem must be of "medium" or "hard" difficulty (no easy stuff!). Also, according to the theme of this season, it must be related to **strings**! Note that for the cops, **efficiency matters most**, and you do not need to spend too much efforts trying to golf up the code painstakingly.

Your answer post should include the following:

1. The problem you chose, and the link to it on LeetCode.
2. Your code, its length in bytes, and the language you used.
3. The UTC time of your post.
4. The time complexity of your code.

The robbers will then try to golf up the cops' code without sacrificing time complexity. Here's the link to the Robbers' Thread.

Your score is the amount of 5 minute intervals in the amount of time it remains uncracked, rounded to the nearest integer!

If you have any advices please let me know in the comments so that this challenge series could be improved. Thanks in advance!

Leaderboard: It seems that I seriously need to fix the scoring system :-( Leaderboard disactivated for this season.

# Answer
# ATOI string to integer, 130 Bytes, Python 3 (IDLE), probably \\$O(n)\\$ or worse, 9:10 am UTC (it's DST in uk), Cracked in 18 min, so ~~0 points :(~~ 4 points under new system :)

```
lambda x:a if-2**31<(a:=int(re.match(r" *((\+|-)?(\d*))",x).groups(1)[0]or 0))<2**31-1else-2**31if-2**31>=a else 2**31-1
import re

```

Don't Try It Online!, it doesn't work there.
> 4 votes

# Answer
# Concatenated Words, Python, 177 bytes, \\$O(n)\\$ time assuming input is a set where \\$n\\$ is the number of words, Cracked by Cursor Coercer, 7 points

This is \\$O(2^L)\\$ where \\$L\\$ is the length of each word but I don't define N that way. It's almost as if asymptotic complexity is isn't a total unambiguous ordering for arbitrary problems.

```
lambda z:[i for i in z if any(all(i[a:b]in z and i[a:b]!=i for a,b in q)for q in g(0,len(i)))]
def g(a,b):
 yield[(a,b)]
 for i in range(a+1,b):
  for j in g(i,b):yield[(a,i)]+j

```

Attempt This Online!

time: 2023-07-20 14:02:05Z
> 4 votes

# Answer
# Removing Stars From a String, C (GCC), 47 bytes, \\$O(n)\\$ complexity, Cracked by jimmy23013, 25 points

```
f(char*s){for(char*p=s;*s-42?*p++=*s:p--;s++);}

```

Attempt This Online!

Time: 2023-07-20 16:36:08Z
> 4 votes

# Answer
# Generate Parenthesis, \>\<\> (Fish), 178 bytes, \\$O(n!)\\$, Cracked by C--

Time: 2023-07-21 12:35:24Z

```

```

Hover over any symbol to see what it does. If this appears glitched unformulated version below.

Try it

If the "fancy" formatting above doesn't display for you, a version without formatting:

```
i>:?v~l2,b2.
10-1<.02}}
:?v~{{l2,06.
v \&'('o:2*[{1+}]$:
\:?v~$}}&1-b2.
')'/.31-1o
>:?v;
1+&\&:2*[{1-:}]?v:@l1-2,&:&-1+=?v$
{{&>:?v~}}50ao./~0}]
.61-1&>1-&:2*[{/>1{{69!.<96{{1~$<

```

If my Interpreter is too slow for you, TIO link

Not super well golfed, relying on people being too intimidated by fish.

## How this works

The standard recursive version doesn't work well for fish because:

* It doesn't have functions
* There is no easy way to copy an array
* The only array type thing you have is the stack and there is only one of them

I came up with a completely different approach that does not involve recursion at all, and uses O(n) memory.

We note that, for a number of parenthesis N, we can place opening parenthesis on fixed places then just dynamically decide where to place the closing one that matches it. We can use this to encode a given configuration as the distance between each opening and the corresponding closing parenthesis (+1 for technical reasons)

```
(())()() = 2, 1, 1, 1
((()())) = 3, 2, 1, 1
(((()))) = 4, 3, 2, 1
()()(()) = 1, 1, 2, 1

```

Now all we need to find is an algorithm that can, from one set of numbers, figure out the "next" valid configuration.

### Rendering

The render loop works as follows: We store next to each number an extra 0. This 0 represents the number of closing parenthesis that need to be drawn after that number. Now, when we for example need to render a parenthesis with a distance of 1, we increment the value in the stack at 2 * 1. In this case it will be the closing parenthesis for the same number. Then after printing the `(` we can print N `)` characters depending on the value stored.

All of this means we can avoid any kind of recursion.

### Incrementing

The incrementing logic is harder, but we can re-use the information from the closing parenthesis from the render stage. First, we try to increment the order of the last opening brace. If this makes us extend past the edge of the set, we skip and go to the next one. This part is easy.

An harder part is making sure the area we enclode does not partially intersect any other pair. There couldn't be any pairs to the right since they have all been reset to 1, but there could be intersecting pairs to the left. For this purpose, we check the closing parenthesis again. We subtract one closing parenthesis from N steps to the front. If they are now zero, we can safely increment past the boudary. Otherwise, we must again reset and try the next pair to the left.

If we have found a opening that can be incremented, we must reset the rest of the ")" counters to 0, then can render and continue. If we have reached the leftmost brace and it also can't be incremented, we have tried all sets and we can safely exit.

## Approximately the same algorithm in Rust

```
|x|{
    let mut z=vec![(1,0);x];
    loop{
        for i in 0..x{
            print!("(");
            let closing_index = z[i].0 + i - 1;
            z[closing_index].1+=1;
            print!("{}",")".repeat(z[i].1));
        }
        let mut done=false;
        for i in 0..x{
            let closing_index =z[i].0 + i - 1;
            z[closing_index].1-=1;
            if !done && !(i + z[i].0 >= x || z[closing_index].1> 0) {
                z[i].0+=1;
                done=true;
            }
        }
        if !done {
            return;
        }
        println!();
    }
}

```
> 4 votes

# Answer
# Edit Distance, Python 3.8 (pre-release), 124 bytes, \\$O(mn)\\$ complexity, cracked by SuperStormer

(I won't bother trying to score since I had to edit my answer and the scoring system was flawed)

```
lambda a,b:(d:=range(len(b)+1),[d:=[x:=d[(j:=0)]+1]+[x:=min(x+1,d[(j:=j+1)]+1,d[j-1]+(i!=k))for k in b]for i in a])and d[-1]

```

Try it online!

Ya like walrus operators?

Complexity is \\$O(mn)\\$ where m,n are the lengths of the two input strings.
Time: 2023-07-20 16:18:22Z
> 3 votes

# Answer
# Simplify Path, 119 Bytes, Python 3, \\$O(n)\\$, 16:20 UTC (cracked by Value Ink, 20 points)

```
def f(p):
    s=[]
    for x in p.split('/'):
        if x=='..'and s:s.pop()
        elif x and x not in'..':s+=[x]
    return f'/{"/".join(s)}'

```
> 3 votes

# Answer
# Python 3, 144 bytes, Longest Substring Without Repeating Characters, O(N), Time: 2023-07-20 17:17:27Z.

# 83 min = 17 points

# Cracked by CursorCoercer (125 bytes)

```
def f(s):
 m=x=y=0;c={0,}
 while y<len(s):
  if s[y]in c:
   while s[x]!=s[y]:x+=1
   x+=1;c={*s[x:y]}
  c.add(s[y]);y+=1;m=max(m,y-x)
 return m

```

Try it online!

Runs in O(N) because python sets have lookup/add of O(1). Using lists could decrease the byte count but would technically increase the runtime to O(N^2)
> 3 votes

# Answer
# Reverse words in string, Python, 47 bytes, \\$O(n)\\$ complexity, Cracked by The Thonnu, 6 point

```
lambda g:print(*map(str.strip,g.split()[::-1]))

```

> Given an input string s, reverse the order of the words.
>
> A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
>
> Return a string of the words in reverse order concatenated by a single space.
>
> Note that `s` may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Time: 2023-07-20 13:35:51Z
> 2 votes

# Answer
# Count and Say, Go, 173 bytes, \\$O(n^2)?\\$, 2023-07-20 21:22:03 UTC

## Cracked by C--, score 5

```
import."fmt"
func g(n int)string{s:="1"
for N:=1;N<n;N++{c,o,f,k:=1,"",rune(s[0]),s[1:]+"_"
for _,r:=range k{if r==f{c++}else{o+=Sprintf("%d%c",c,f);f,c=r,1}}
s=o}
return s}

```

Attempt This Online!

A slight modification of my Say What You Can See answer. Enjoy Golang!
> 2 votes

# Answer
# Python, 47 bytes, Spiral Matrix, `O((m+n)mn)`

```
f=lambda x:x and[*x[0]]+f([*zip(*x[1:])][::-1])

```

> Given an m x n matrix, return all elements of the matrix in spiral order.

Time: 2023-07-21 08:54:05Z
> 2 votes

# Answer
# Repeated String Match, 48 bytes, Excel, 20:08 UTC, *O*(*n*)

```
=IFNA(XMATCH(0,0*FIND(B1,REPT(A1,ROW(A:A)))),-1)

```

Inputs: *a* and *b* in cells `A1` and `B1` respectively.
> 1 votes

# Answer
# Generate Parenthesis, Rust, 193 bytes, \\$O(n!)\\$ Cracked by C--, 1 point

* C-- generously helped me save 1 point before cracking it in an actually significant way

```
fn f(z:i32)->Vec<String>{if z<1{vec![format!("")]}else{(0..z).flat_map(|i|->Vec<_>{let(a,b)=(f(i),f(z-i-1));a.iter().flat_map(|c|b.iter().map(move|d|format!("({c})")+d)).collect()}).collect()}}

```

Attempt This Online!

Time: 2023-07-21 05:01:42Z
> 1 votes

# Answer
# Sum of Scores of Built Strings, C (GCC), 71 bytes, \\$O(n^2)\\$ complexity, Cracked by mousetail, 93 points

```
f(s,l,i)char*s;{for(i=0;s[i]&&s[l+i]==s[i];++i);return l?i+f(s,l-1):i;}

```

Attempt This Online!

Time: 2023-07-20 21:33:27Z
> 1 votes

# Answer
# Ruby, 184 bytes, Substring with Concatenation of All Words

```
->s,d{l,*r=d.size*z=d[0].size
c={};d.map{|w|c[w]=d.count w}
0.step(z-1){|i|j=i;b=Hash.new 0
(r<<j-l if c.all?{|w,v|v==b[w]}
b[s[j-l,z]]-=1if j>=l
b[s[j,z]]+=1
j+=z)while j<s.size+l}
r}

```

Try it online!

Complexity should be \\$O(mn)\\$ where \\$m\\$ is the number of *unique* words (relevant for a testcase on LeetCode where the words list has multiple copies of "a") and \\$n\\$ is the length of the string.

Current time is 2023-07-21 00:04 UTC
> 1 votes

# Answer
# Python, 48 bytes, Count Number of Distinct Integers After Reverse Operations, `O(nd)`

```
lambda x:len({*x}|{int(str(c)[::-1])for c in x})

```

> You are given an array nums consisting of positive integers.
>
> You have to take each integer in the array, reverse its digits, and add it to the end of the array. You should apply this operation to the original integers in nums.
>
> Return the number of distinct integers in the final array.

Time complexity is `O(nd)` where n is the number of elements in the input, and d is the number of digits in the largest number.

Time of post: 2023-07-21 08:21:19Z
> 0 votes

---
Tags: code-golf, string, cops-and-robbers, fastest-algorithm
---


title: Nobody knows GAU Numbers

text:
# Question
Title: Nobody knows GAU Numbers
# Let me introduce you to GAU numbers

```
GAU(1) = 1
GAU(2) = 1122
GAU(3) = 1122122333
GAU(4) = 11221223331223334444
GAU(6) = 11221223331223334444122333444455555122333444455555666666
...
GAU(10) = 11221223331223334444122333444455555122333444455555666666122333444455555666666777777712233344445555566666677777778888888812233344445555566666677777778888888899999999912233344445555566666677777778888888899999999910101010101010101010

```

# **This challenge is pretty simple!**

Given an integer n\>0, find the number of digits of GAU(n)

# Example

Let's make **GAU(4)**
we take the following steps (until we get to 4) and concatenate them

```
[1][122][122333][1223334444]

```

you must write every number as many times as its value, but you have to count every time from 1

Let's try to make **GAU(5)**
we will have to count from 1 to 1

```
[1]

```

then from 1 to 2 (but **repeating every number as many times as its value**)

```
[122]

```

then from 1 to 3

```
[122333]

```

then from 1 to 4

```
[1223334444]

```

and finally from 1 to 5 (this is the **last step** because we want to find GAU(**5**))

```
[122333444455555]

```

Now we take all these steps and concatenate them
the result is GAU(5)

```
11221223331223334444122333444455555

```

**We are interested in the number of digits of these GAU numbers.**

# Test cases

***Input⟼Output***

```
n   ⟼ Length(GAU(n))

1   ⟼ 1
2   ⟼ 4
3   ⟼ 10
10  ⟼ 230
50  ⟼ 42190
100 ⟼ 339240
150 ⟼ 1295790

```

This is a challenge.
Shortest code in bytes will win.

If you still have any questions please let me know.
I really want everyone here to understand this magic-hidden-complex pattern

# Answer
# SOGL V0.12, ~~11~~ ~~10~~ ~~8~~ ~~7~~ 5 bytes

```
∫∫l*+

```

Try it Here! \- this expects to be called as a function with the input on the stack and the input box empty.
7 byte alternative taking the input from the input box:

```
0.∫∫l*+

```

Try it Here!

```
0      push 0
 .     push the input
  ∫    iterate over a range 1..POP (input) inclusive, pusing the current number
   ∫    iterate over 1..POP (above loops number) inclusive, pusing the current number
    l    push that numbers length without popping the number
     *   multiply the length by the number
      +  add to the zero, or whatever it is now

```
> 14 votes

# Answer
# Haskell, 45 bytes

```
f n=sum[j*length(show j)|i<-[1..n],j<-[1..i]]

```

Try it online!
> 8 votes

# Answer
# Brain-Flak, 166 bytes

```
<>(((()()())({}){})())<>{({}[()]<({}({}<<>({}[()])((){[()](<()>)}{}){{}((((({})({})){}{}){}))<>(({}<({}())>){()<({}[({})])>}{})(<>)}{}<>>({}({})())))>)}{}({}<{}{}{}>)

```

Try it online!

### Explanation

```
<>(((()()())({}){})())<>           # Initialize second stack with 9 and 10
{({}[()]<                          # Do main loop n times:
  ({}
    ({}
      <
        <>({}[()])                 # Subtract 1 from counter to next power of 10
        ((){[()](<()>)}{}){        # If reached a power of 10 (say, 10^k):
          {}((((({})({})){}{}){})) # Multiply existing (10^k*0.9) by 10 and push twice
          <>                       # On first stack
          (
            ({}<({}())>)           # Increment length of numbers
            {()<({}[({})])>}{}     # Divide length of new set of numbers by this length
          )                        # Add together to get new set of numbers length
        (<>)}
      {}<>>
      ({}({})())                   # Add number length to number set length
    )                              # Add number set length to new segment length
  )                                # Add new segment length to total length
>)}                                # End main loop
{}({}<{}{}{}>)                     # Put result on stack by itself

```
> 7 votes

# Answer
# Husk, 5 bytes

```
ṁLΣQḣ

```

Try it online!

**Explanation**

```
ṁ  map over
 L  length
  Σ  sum list
   Q  all sublists
    ḣ  range 1 .. N

```
> 7 votes

# Answer
# Jelly, 7 bytes

```
Rx`ƤDFL

```

Try it online!
> 4 votes

# Answer
# 05AB1E, 5 bytes

```
LŒJJg

```

Try it online!

**Explanation**

```
L      # push [1 .. a]
 Œ     # all substrings (a)
  J    # numbers to strings (inner)
   J   # numbers to strings (outer)
    g  # length

```
> 4 votes

# Answer
# Python 2, 53 bytes

```
lambda x:sum(len(`i`)*i*(x-i+1)for i in range(1,x+1))

```

Try it online!
> 3 votes

# Answer
# Husk, 7 bytes

```
ṁLṁṘNḣḣ

```

Try it online!

### Explanation

```
          Implicit input, e.g 4
      ḣ   Range from 1 to n                               [1,2,3,4]
     ḣ    Prefixes                                        [[],[1],[1,2],[1,2,3],[1,2,3,4]]
  ṁ       Map and then concatenate
   ṘN     Repeat each number in each list by its index    [[],[1],[1,2,2],[1,2,2,3,3,3],[1,2,2,3,3,3,4,4,4,4]]
                                                          [1,1,2,2,1,2,2,3,3,3,1,2,2,3,3,3,4,4,4,4]
ṁ         Map and then sum
 L        Length (of number: 10 -> 2)                     26

```
> 3 votes

# Answer
# Husk, 7 bytes

```
Σ∫mS*Lḣ

```

Try it online!

### Ungolfed/Explanation

```
         -- implicit input N                        | 10
  m   ḣ  -- map the following function over [1..N]  | [1,2,3,4]
   S*L   --   multiply length of number by itself   | [1,2,3,4] (only important for numbers ≥ 10)
 ∫       -- prefix sums                             | [0,1,3,6,10]
Σ        -- sum                                     | 20

```
> 3 votes

# Answer
# Python 2, ~~59~~ 58 bytes

*Another one bytes the dust thanks to Jonathan Frech.*

```
f=lambda n:n and sum(i*len(`i`)for i in range(n+1))+f(n-1)

```

Try it online!

Not short but eh... what the heck.
> 3 votes

# Answer
# JavaScript (ES6), ~~57~~ 55 bytes

```
n=>[...Array(n)].reduce(x=>x+(++y+"").length*y*n--,y=0)

```

Try it online!
> 3 votes

# Answer
# CJam, 20 bytes

```
q~),(\{),{_s,*+}*+}%

```

Try it online!

The number is passed in the "input" field.

Ungolfed explanation: (example input = 2)

```
q~),(\{),{_s,*+}*+}%                                             | Stack:
q                     read input as string                       | "2"
 ~                    eval input (add it to stack as integer)    | 2
  )                   add 1                                      | 3
   ,                  range (convert to array with values 0...N) | [0, 1, 2]
    (                 pop first item of array                    | [1, 2] 0
     \                swap top two values of stack               | 0 [1, 2]
      {           }   for each item in array...                  | 0 1
       )              add 1                                      | 0 2
        ,             range (convert to array with values 0...N) | 0 [0, 1]
         {     }      for every element in the array...          | 0 0
          _           duplicate                                  | 0 0 0
           s          convert to string                          | 0 0 "0"
            ,         get length of string                       | 0 0 1
             *        multiply                                   | 0 0
              +       add                                        | 0 1
                *     fold                                       | 0 1
                 +    add                                        | 1
                   %  repeat                                     | 4

```

It seems hard when explained lol.
> 3 votes

# Answer
# , 39 bytes

```
function(n)sum(nchar(rep(1:n,n:1*1:n)))

```

Verify all test cases!

Simple algorithm; I observed, as most did, that for `i` in `1:n`, `i` is repeated `i*(n-i+1)` times. So I create that vector, count the number of characters in each, and sum them.
> 2 votes

# Answer
# JavaScript (ES6), ~~50~~ 42 bytes

*Updated: now basically a port of what other answers are doing.*

```
f=(n,i=1)=>n&&`${n}`.length*n*i+f(n-1,i+1)

```

### Test cases

```
f=(n,i=1)=>n&&`${n}`.length*n*i+f(n-1,i+1)

console.log(f(1))   // 1
console.log(f(2))   // 4
console.log(f(3))   // 10
console.log(f(10))  // 230
console.log(f(50))  // 42190
console.log(f(100)) // 339240
console.log(f(150)) // 1295790
```
> 2 votes

# Answer
# J, 24 bytes

```
[:+/[:+/\[:(*#@":"0)1+i.

```

Similar high-level approach to dzaima's APL answer, translated into J, except we calculate the number's length by turning it into a string first instead of taking logs, and we get to use J's hook to multiply that length by the number itself: `(*#@":"0)`. After that it's just the sum of the scan sum.

Try it online!
> 2 votes

# Answer
# Perl 6, 36 bytes

```
{[+] 1..*Z*($_...1).map:{.chars*$_}}

```

Test it

## Expanded:

```
{  # bare block lambda with implicit parameter ｢$_｣

  [+]               # reduce the following using &infix:«+»

    1 .. *          # Range from 1 to infinity

    Z*              # zip using &infix:«*»

    ( $_ ... 1 )    # sequence from the input down to 1
    .map:           # for each one
    { .chars * $_ } # multiply the number of digits with itself
}

```
> 2 votes

# Answer
# Röda, 31 bytes

```
{f={seq 1,_}f|f|[#`$_`*_1]|sum}

```

Try it online!
> 2 votes

# Answer
# Python 2, 51 50 bytes

```
lambda n:sum(~k*(k-n)*len(`k+1`)for k in range(n))

```
> 1 votes

# Answer
# \[Dyalog APL\], ~~22~~ 20 bytes

```
{+/≢¨⍕¨↑,/(/⍨¨⍳¨⍳⍵)}

```

Try it online!

Explanation:

```
{+/≢¨⍕¨↑,/(/⍨¨⍳¨⍳⍵)}
{                  } anonymous function with right argument named ⍵
                ⍳⍵   range 1 to right arg
              ⍳¨     for each, range 1 to it
             ¨       for each
           /⍨          for each item, repeat right arg left arg times
          (       )  take that and
        ,/           join the sub-arrays together
       ↑             convert from a nested array to a simple array (or something like that, I don't quite understand it :p)
     ⍕¨              convert each number to a char-array (aka string version)
   ≢¨                get length of each
 +/                  sum that together

```
> 1 votes

# Answer
# Mathematica, 66 bytes

```
Tr[1^(f=Flatten)[IntegerDigits/@f@(a=Array)[a[#~Table~#&,#]&,#]]]&

```
> 1 votes

# Answer
# Japt, ~~12~~ ~~11~~ ~~10~~ 9 bytes

```
õõÈ*sÊÃxx

```

Try it or test all numbers from 1 to 150.

---

## Explanation

Implicit input of integer `U`.

```
õõ

```

Generate an array of integers from 1 to `U` and then generate sub-arrays from 1 to each integer.

```
È   Ã

```

Pass the elements of each sub-array through a function.

```
*sÊ

```

Convert the current element to a string (`s`), get it's length (`Ê`) and multiply it by the element.

```
xx

```

Reduce the main array by addition after first doing the same to each sub-array.
> 1 votes

# Answer
# Excel VBA, <sub>~~66~~ ~~51~~</sub> 50 Bytes

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

```
For i=1To[A1]:For j=1To i:s=s+j*Len(j):Next j,i:?s

```

## Alternate Version, 94 Bytes

Anonymous VBE immediate window function that takes input,`n`, from range `[A1]` constructs the `GUA(n)` and outputs the length of it to the VBE immediate window

```
[B1].Resize([A1],1)="=IfError(Offset(B1,-1,0)&Rept(Row(),Row()),1)":?[Len(TextJoin("",1,B:B))]

```
> 1 votes

# Answer
# QBIC, 21 bytes

```
[:|[a|[c|A=A+!c$}?_lA

```
> 1 votes

# Answer
# Charcoal, ~~18~~ 14 bytes

```
ＩΣＥ⊕ＮΣＥ⊕ι×λＬＩλ

```

Try it online! Link is to verbose version of code. Edit: Using `Sum` saved me 4 bytes. Explanation:

```
  Ｅ⊕Ｎ           Map from 0 to the input (loop variable i)
      Ｅ⊕ι       Map from 0 to i (loop variable l)
            Ｉλ  Cast l to string
           Ｌ    Take the length
         ×λ     Multiply by l
     Σ          Sum the results
 Σ              Sum the results
Ｉ               Cast to string
                Implicitly print

```
> 1 votes

# Answer
# Actually, 13 bytes

```
R♂R♂i⌠;n⌡Mεjl

```

Try it online!

Explanation:

```
R♂R♂i⌠;n⌡Mεjl
R              range(1, n+1)
 ♂R            range(1, x+1) for x in previous
   ♂i          flatten into 1D list
     ⌠;n⌡M     for x in list:
      ;n       repeat x x times
          εj   concatenate to string
            l  length

```
> 1 votes

# Answer
# Jq 1.5, ~~82~~ ~~49~~ 43 bytes

```
[range(.)+1|range(.)+1|"\(.)"*.|length]|add

```

Expanded

```
[   range(.)+1        # for i=1 to N
  | range(.)+1        # for j=1 to i
  | "\(.)"*.          # "j" copied j times
  | length            # convert to length
] | add               # add lengths

```

Sample Run

```
$ jq -Mr '[range(.)+1|range(.)+1|"\(.)"*.|length]|add' <<< "150"
1295790

```

Try it online! also jqplay.org
> 1 votes

# Answer
# C# (.NET Core), 94 80 74 bytes

```
n=>{int b=0,a=0,i;while(a++<n)for(i=0;i++<a;)b+=(i+"").Length*i;return b;}

```

Try it online!

I was hoping to find a direct solution like what @kamoroso94's answer started, but gave up as I was spending too much time on it. There probably is a way of doing it, but the formula needs to adjust for every magnitude step.

### Acknowledgements

14 bytes saved thanks to @someone

6 bytes saved thanks to @Kevin Cruijssen
> 1 votes

# Answer
# Ruby, 73 bytes

```
f=->(t){(1..t).map{|n|(1..n).map{|n|Array.new(n,n)}}.flatten.join.length}

```
> 1 votes

# Answer
# Stacked, 28 bytes

```
[~>[~>[:rep]"!]"!flat''#`#']

```

Try it online!

Some might ask, "At which point are aliases unreadable?" If this isn't close, you have a very liberal definition of "readability".

## Explanation

```
[~>[~>[:rep]"!]"!flat''#`#']    input: N
 ~>[          ]"!               for each number K from 1 to N
    ~>[    ]"!                  for each number J from 1 to K
       :rep                     repeat J J times
                 flat           flatten the resultant array
                     ''#`       join by the empty string
                         #'     get the length of said string

```
> 1 votes

# Answer
# Ruby, ~~41~~ 40 bytes

```
->n{(1..n).map{|x|[x]*x*=-x-~n}*''=~/$/}

```

Try it online!
> 1 votes

# Answer
# MATL, 15 bytes

```
:ttP*Y"10&YlQks

```

Try it online!

Explanation:

```
:                range 1:input (implicit input)
 tt              duplicate twice
   P             reverse
    *            multiply elementwise
     Y"          runlength decoding
       10&Yl     log10
            Qk   increment and floor
              s  sum (implicit output)

```
> 1 votes

# Answer
# Bash, ~~48~~, 44 bytes

Saved 4 bytes thanks to for + curly braces trick

```
for((;r+=t+=n*${#n},++n<=$1;));{ :;};echo $r

```
> 1 votes

# Answer
# Ohm v2, 7 bytes

```
@@D×JJl

```

Try it online!
> 1 votes

# Answer
# Thunno 2 `JL`, 3 bytes

```
RJF

```

Try it online!

Or, 5 bytes flagless: `RJFJl`

#### Explanation

```
RJFJl  # Implicit input
R      # Range [1..input]
 J     # Join into a string
  F    # All substrings
   J   # Join into a string
    l  # Length of the string
       # Implicit output

```
> 1 votes

# Answer
# Python 3, 47 bytes

```
f=lambda x,i=1:x and x*i*len(str(x))+f(x-1,i+1)

```

Try it online!
> 0 votes

# Answer
# Mathematica, 34 bytes

```
Sum[i⌊1+Log10@i⌋,{j,#},{i,j}]&

```
> 0 votes

# Answer
# Perl 5, 33 + 1 (-p) = 34 bytes

```
map{map$\+=$_*y///c,1..$_}1..$_}{

```

Try it online!
> 0 votes

# Answer
# 05AB1E, 6 bytes

```
LLD×Jg

```

Try it online!

**Explanation**

```
L        # range [1 ... input]
 L       # for each range [1 ... x]
  D      # duplicate
   ×     # repeat each in the first list a number of times determined by the second list
    J    # join to string
     g   # length

```
> 0 votes

# Answer
# Kotlin, 36 bytes

```
{x:Int->(1..x).flatMap{1..it}.sum()}

```

Test:

```
val GAU = {x:Int->(1..x).flatMap{1..it}.sum()}
GAU(5)
=> 35

```
> 0 votes

# Answer
# RProgN 2, 12 bytes

```
{{]Ø.*}S.}S.

```

Try it online!
> 0 votes

# Answer
# Java 8, 76 bytes

```
n->{int r=0,i=0,j;for(;i++<n;)for(j=0;j++<i;r+=(j+"").length()*j);return r;}

```

I have the feeling this can be golfed with a more arithmetic approach, instead of using `String#length`..

**Explanation:**

Try it here.

```
n->{                        // Method with integer as both parameter and return-type
  int r=0,                  //  Result-integer
      i=0,j;                //  Index integers
  for(;i++<n;)              //  Loop (1) from 0 to the input (exclusive)
    for(j=0;                //   Reset `j` to 0
        j++<i;              //   Inner loop (2) from 0 to `i` (exlusive)
      r+=                   //    Append the result-String with:
         (j+"").length()*j  //     The length of `j` multiplied by `j`
    );                      //   End of inner loop (2)
                            //  End of inner loop (1) (implicit / single-line body)
  return r;                 //  Return result-String
}                           // End of method

```
> 0 votes

# Answer
# Scala, 44 bytes

```
(1 to n).map(i=>(i+"").length*i*(n+1-i)).sum

```

Try it online!
> 0 votes

# Answer
# Jelly, 7 bytes

```
RRx`€VV

```

Try it online!

**Explanation:**

```
RRx`€VV    Example input: 3
R          Range. Result: [1, 2, 3]
 R         Range (vectorizes). Result: [[1], [1, 2], [1, 2, 3]]
    €      Apply to €ach...
  x`       Repeat each number itself times. Result: [[[1]], [[1], [2, 2]], [[1], [2, 2], [3, 3, 3]]]
     VV    Concatenate them into one big friendly number. Result: 1122122333

```
> 0 votes

# Answer
## PocoLithp, 111 bytes

```
(define gau(#(N I)(if(!(defined I))(gau N 1)(if(!= N 0)(+(*(*(length(expl(str N)))N)I)(gau(- N 1)(+ I 1)))N))))

```

More readable version:

```
(define gau (# (N I) (begin
        (if (! (defined I))      ;; I not supplied, recurse with I set to 1
                (gau N 1)
                (begin           ;; I supplied, calculate
                        (define A (length (expl (str N))))  ;; `N`.length
                        (if (!= N 0)
                            ;; N != 0, head recursive calculation
                            (+ (* (* A N) I) (gau (- N 1) (+ I 1)))
                            ;; N == 0, return it
                             N)
                )
        )
)))

```

Usage:

```
(gau 123) => 662505
(gau 256) => 7532088

```

Named function `gau`, which takes 1 or 2 parameters. If called with 1 parameter, calls self with 2nd parameter set to 1. This implements the default variables used in other implementations.

This could possibly be made tail recursive, but it would likely be even longer than it already is.
> 0 votes

# Answer
# Powershell, 93 bytes

```
$a=@();$b=@();1..$n|% $_{$i=0;Do{$a+=$_;$i++}while($i-ne$_);$b+=$a-join''};($b-join'').Length

```

Code exploded a bit:

```
$inputNum = 10
$numbers = 1..$inputNum
$array = @()
$bigArray = @()
Foreach ($number in $numbers){
    $i = 0
    Do {
        $array += $number
        $i++
    }
    while ($i -ne $number)
    $bigArray += $array -join ''
}
($bigArray -join '').Length

```
> 0 votes

# Answer
## Retina, 29 bytes

```
.+
$*
1
1$`¶
1
1$%`¶
1
$.%_
.

```

Try it online!

### Explanation

```
.+
$*

```

Convert input to unary.

```
1
1$`¶

```

Turn the input `N` into a range from `1` to `N` by inserting the prefix up to each `1` after it, together with a linefeed.

```
1
1$%`¶

```

Do the same thing to each value in that range. This time we use `$%``, which is just the prefix on the current line. So this gives `1, 1,2, 1,2,3, 1,2,3,4, ...` (in unary). Now all we need to do is repeat each value accordingly and converting to decimal.

```
1
$.%_

```

This is done by replacing each `1` with the length of the line its on.

```
.

```

Finally we count the number of digits.
> 0 votes

# Answer
# J-uby, 32 bytes

```
:+|:*&(:+|:*&~:*%-[I])|:join|:+@

```

Attempt This Online!

## Explanation

```
:+ | :* & (:+ | :* & ~:* % -[I]) | :join | :+@

:+ | :* & (                    )                # Range, then map with...
           :+ | :* &                            #   Range, then map with...
                     ~:* % -[I]                 #     [n] * n
                                 | :join | :+@  # Then join all elements and get length

```
> 0 votes

---
Tags: code-golf, sequence
---