title: Apportionment paradox

text:
# Question
Title: Apportionment paradox
Given:

* A natural number **S**.
* A list of N rational weights **W** that sum to 1.

Return a list **L** of N non-negative integers, such that:

```
(1) sum(L) = S
(2) sum((S⋅W_i - L_i)^2) is minimal

```

In other words, approximate `S⋅W_i`s with integers as closely as possible.

Examples:

```
1 [0.4 0.3 0.3] = [1 0 0]
3 [0 1 0] = [0 3 0]
4 [0.3 0.4 0.3] = [1 2 1]
5 [0.3 0.4 0.3] = [2 2 1] or [1 2 2] but not [1 3 1]
21 [0.3 0.2 0.5] = [6 4 11]
5 [0.1 0.2 0.3 0.4] = [1 1 1 2] or [0 1 2 2]
4 [0.11 0.3 0.59] = [1 1 2]
10 [0.47 0.47 0.06] = [5 5 0]
10 [0.43 0.43 0.14] = [4 4 2]
11 [0.43 0.43 0.14] = [5 5 1]

```

Rules:

* You can use any input format at all, or just provide a function that accepts the input as arguments.

Background:

This problem comes up when displaying **S** of different types of items in different proportions **Wi** with regard to the types.

Another example of this problem is proportional political representation, see the apportionment paradox. The last two test cases are known as Alabama paradox.

> As a statistician, I recognised this problem as equivalent to a problem encountered in identifying sample sizes when conducting a stratified sample. In that situation, we want to make the proportion of each stratum in the sample equal to the proportion of each stratum in the population. — @tomi

# Answer
# APL, 21

```
{{⍵+1=⍋⍋⍵-⍺}⍣⍺/⍺0×⊂⍵}

```

This is a translation from aditsu's 37 byte CJam answer.

Test it online.

### Explanation

```
 {      ⍵-⍺}            ⍝ Right argument - left argument.
 {  1=⍋⍋⍵-⍺}            ⍝ Make one of the smallest number 1, others 0.
 {⍵+1=⍋⍋⍵-⍺}            ⍝ Add the result and the right argument together.
 {⍵+1=⍋⍋⍵-⍺}⍣⍺          ⍝ Repeat that S times. The result of each iteration is the new right argument.
                  ⊂⍵    ⍝ Return enclosed W, which is taken as one unit in APL.
               ⍺0×⊂⍵    ⍝ Return S*W and 0*W.
{{⍵+1=⍋⍋⍵-⍺}⍣⍺/⍺0×⊂⍵}   ⍝ Make S*W the left argument, 0*W the right argument in the first iteration.

```
> 6 votes

# Answer
# Python 2, ~~95~~ ~~83~~ ~~132~~ ~~125~~ 143

My first (and second) (and third) algorithm had problems so after a (another!) rewrite and more testing, here is (I really hope) a correct and fast solution:

```
def a(b,h):
 g=h;c=[];d=[]
 for w in b:f=int(w*h);d+=[f];c+=[h*w-f];g-=f
 if g:
  for e in sorted(c)[-g:]:i=c.index(e);c[i]=2;d[i]+=1
 return d

```

The source before the minifier now looks like:

```
# minified 143 bytes
def golfalloc(weights, num):
    # Tiny seq alloc for golfing
    gap = num;
    errors = [];
    counts = []
    for w in weights :
        count = int(w*num);
        counts += [count];
        errors += [num*w - count];
        gap -= count
    if gap:
        for e in sorted(errors)[-gap:] :
            i = errors.index(e);
            errors[i] = 2;
            counts[i] += 1
    return counts

```

The tests return:

```
Pass                    Shape    N               Result Error                        AbsErrSum
ok            [0.4, 0.3, 0.3]    1            [1, 0, 0] -0.60,+0.30,+0.30                 1.20
ok                  [0, 1, 0]    3            [0, 3, 0] +0.00,+0.00,+0.00                 0.00
ok            [0.3, 0.4, 0.3]    4            [1, 2, 1] +0.20,-0.40,+0.20                 0.80
ok            [0.3, 0.4, 0.3]    5            [2, 2, 1] -0.50,+0.00,+0.50                 1.00
ok            [0.3, 0.2, 0.5]   21           [6, 4, 11] +0.30,+0.20,-0.50                 1.00
ok       [0.1, 0.2, 0.3, 0.4]    5         [1, 1, 1, 2] -0.50,+0.00,+0.50,+0.00           1.00
ok          [0.11, 0.3, 0.59]    4            [1, 1, 2] -0.56,+0.20,+0.36                 1.12
ok         [0.47, 0.47, 0.06]   10            [5, 5, 0] -0.30,-0.30,+0.60                 1.20
ok         [0.43, 0.43, 0.14]   10            [4, 4, 2] +0.30,+0.30,-0.60                 1.20
ok         [0.43, 0.43, 0.14]   11            [5, 5, 1] -0.27,-0.27,+0.54                 1.08

```

This algorithm is similar to other answers here. It is O(1) for num so it has the same run time for integers 10 and 1000000. It is theoretically O(nlogn) for the number of weights (because of the sort). If this withstands all other tricky input cases, it will replace the algorithm below in my programming toolbox.

Please don't use that algorithm with anything not golfy. I made compromises in speed to minimise source size. The following code uses the same logic but is much faster and more useful:

```
def seqalloc(anyweights, num):
    # Distribute integer num depending on weights.
    # weights may be non-negative integers, longs, or floats.
    totalbias = float(sum(anyweights))
    weights = [bias/totalbias for bias in anyweights]
    counts = [int(w*num) for w in weights]
    gap = num - sum(counts)
    if gap:
        errors = [num*w - q for w,q in zip(weights, counts)]
        ordered = sorted(range(len(errors)), key=errors.__getitem__)
        for i in ordered[-gap:]:
            counts[i] += 1
    return counts

```

The value of num doesn't affect speed significantly. I have tested it with values from 1 to 10^19. The execution time varies linearly with the number of weights. On my computer it takes 0.15 seconds with 10^5 weights and 15 seconds with 10^7 weights. Note that the weights are not restricted to fractions that sum to one. The sort technique used here is also about twice as fast as the traditional `sorted((v,i) for i,v in enumerate...)` style.

### Original Algorithm

This was a function in my toolbox, modified a little for golf. It was originally from a SO answer. And it is wrong.

```
def seqalloc(seq, num):
    outseq = []
    totalw = float(sum(seq))
    for weight in seq:
        share = int(round(num * weight / totalw)) if weight else 0
        outseq.append(share)
        totalw -= weight
        num -= share
    return outseq

```

It gives an approximation, but is not always correct, although the sum(outseq) == num is maintained. Fast but not recommended.

Thanks to @alephalpha and @user23013 for spotting the errors.

EDIT: Set totalw (d) to be 1 as OP specifies the sum of weights will always be 1. Now 83 bytes.

EDIT2: Fixed bug found for \[0.4, 0.3, 0.3\], 1.

EDIT3: Abandoned flawed algorithm. Added better one.

EDIT4: This is getting ridiculous. Replaced with correct (I really hope so) algorithm.

EDIT5: Added not-golfy code for others that may like to use this algorithm.
> 7 votes

# Answer
# Mathematica, ~~67~~ ~~50~~ ~~46~~ 45 chars

```
f=(b=⌊1##⌋;b[[#~Ordering~-Tr@#&[b-##]]]++;b)&

```

Ungolfed:

```
f[s_, w_] := Module[{a = s*w, b, c, d},
  b = Floor[a];
  c = b - a;
  d = Ordering[c, -Total[c]];
  b[[d]] += 1;
  b]

```

Example:

```
f[5,{0.1,0.2,0.3,0.4}]

```

> {1, 1, 1, 2}
> 4 votes

# Answer
# CJam - 37

```
q~:W,0a*\:S{[_SWf*]z::-_:e<#_2$=)t}*p

```

Try it online

**Explanation:**

```
q~             read and evaluate the input
               (pushing the number and the array on the stack)
:W,            save the array in variable W and calculate its length (N)
0a*            make an array of N zeros (the initial "L")
\:S            swap it with the number and save the number in S
{…}*           execute the block S times
    [_SWf*]    make a matrix with 2 rows: "L" and S*W
    z          transpose the matrix, obtaining rows of [L_i S*W_i]
    ::-_       convert to array of L_i-S*W_i and duplicate
    :e<        get the smallest element
    #          find its index in the unsorted array,
               i.e. the "i" with the largest S*W_i-L_i
    _2$=)t     increment L_i
p              print the result nicely

```

**Notes:**

* The complexity is about O(S\*N), so it gets really slow for large S
* CJam is sorely lacking arithmetic operators for 2 arrays, something I plan to implement later

**Different idea - 46**

```
q~:Sf*_:m[_:+S\-@[1f%_,,]z{0=W*}$<{1=_2$=)t}/p

```

Try it online

This is much more straightforward and efficient, but alas, quite a bit longer. The idea here is to start with L\_i=floor(S\*W\_i), determine the difference (say D) between S and their sum, find the D indices with the largest fractional part of S\*W\_i (by sorting and taking top D) and increment L\_i for those indices. Complexity O(N\*log(N)).
> 3 votes

# Answer
# JavaScript (ES6) 126 ~~130 104 115 156 162 194~~

After all the comments and test cases in @CarpetPython's answer, back to my first algorithm. Alas, the smart solution does not work. Implementation shortened a little, it still tries all the possible solutions, calc the squared distance and keep the minimum.

*Edit* For each output element of weight w, 'all' the possible values are just 2: trunc(w\*s) and trunc(w\*s)+1, so there are just (2\**elemensts) possible solutions to try.

```
Q=(s,w)=>
  (n=>{
    for(i=0;
        r=q=s,(y=i++)<1<<w.length;
        q|r>n||(n=r,o=t))
      t=w.map(w=>(f=w*s,q-=d=0|f+(y&1),y/=2,f-=d,r+=f*f,d));
  })()||o

```

**Test** In Firefox/FireBug console

```
;[[ 1,  [0.4, 0.3, 0.3]      ]
, [ 3,  [0, 1, 0]            ]
, [ 4,  [0.3, 0.4, 0.3]      ]
, [ 5,  [0.3, 0.4, 0.3]      ]
, [ 21, [0.3, 0.2, 0.5]      ]
, [ 5,  [0.1, 0.2, 0.3, 0.4] ]
, [ 4,  [0.11, 0.3, 0.59]    ]
, [ 10, [0.47, 0.47, 0.06]   ]
, [ 10, [0.43, 0.43, 0.14]   ]
, [ 11, [0.43, 0.43, 0.14]   ]]
.forEach(v=>console.log(v[0],v[1],Q(v[0],v[1])))

```

*Output*

```
1 [0.4, 0.3, 0.3] [1, 0, 0]
3 [0, 1, 0] [0, 3, 0]
4 [0.3, 0.4, 0.3] [1, 2, 1]
5 [0.3, 0.4, 0.3] [1, 2, 2]
21 [0.3, 0.2, 0.5] [6, 4, 11]
5 [0.1, 0.2, 0.3, 0.4] [0, 1, 2, 2]
4 [0.11, 0.3, 0.59] [1, 1, 2]
10 [0.47, 0.47, 0.06] [5, 5, 0]
10 [0.43, 0.43, 0.14] [4, 4, 2]
11 [0.43, 0.43, 0.14] [5, 5, 1]

```

~~That's a smarter solution. Single pass on weigth array.
For each pass i find the current max value in w. I change this value in place with the weighted integer value (rounded up), so if s==21 and w=0.4, we got 0.5\*21 -\> 10.5 -\> 11. I store this value negated, so it can't be found as max in the next loop. Then I reduce the total sum accordingly (s = s-11) and also reduce the total of the weigths in variable f.
The loop ends when ther is no max above 0 to be found (all the values != 0 have been managed).
At last I returns the values changed to positive again. **Warning** this code modifies the weights array in place, so it must be called with a copy of original array~~

~~```
F=(s,w)=>
 (f=>{
  for(;j=w.indexOf(z=Math.max(...w)),z>0;f-=z)
    s+=w[j]=-Math.ceil(z*s/f);
 })(1)||w.map(x=>0-x)

```~~

**My first try**

Not so a smart solution. For every possible result, it evaluates the difference, and keeps the minimum.

```
F=(s,w,t=w.map(_=>0),n=NaN)=>
  (p=>{
    for(;p<w.length;)
      ++t[p]>s?t[p++]=0
      :t.map(b=>r+=b,r=p=0)&&r-s||
        t.map((b,i)=>r+=(z=s*w[i]-b)*z)&&r>n||(n=r,o=[...t])
  })(0)||o

```

**Ungolfed** And explained

```
F=(s, w) =>
{
  var t=w.map(_ => 0), // 0 filled array, same size as w
      n=NaN, // initial minumum NaN, as "NaN > value"  is false for any value
      p, r
  // For loop enumerating from [1,0,0,...0] to [s,s,s...s]
  for(p=0; p<w.length;)
  {
    ++t[p]; // increment current cell
    if (t[p] > s)
    {
      // overflow, restart at 0 and point to next cell
      t[p] = 0;
      ++p;
    }
    else
    {
      // increment ok, current cell is the firts one
      p = 0;
      r = 0;
      t.map(b => r += b) // evaluate the cells sum (must be s)
      if (r==s)
      {
        // if sum of cells is s
        // evaluate the total squared distance (always offset by s, that does not matter)
        t.map((b,i) => r += (z=s*w[i]-b)*z)
        if (!(r > n))
        {
          // if less than current mininum, keep this result
          n=r
          o=[...t] // copy of t goes in o
        }
      }
    }
  }
  return o
}

```
> 3 votes

# Answer
# CJam, 48 bytes

A straight forward solution to the problem.

```
q~:Sf*:L,S),a*{m*{(+}%}*{1bS=},{L]z::-Yf#:+}$0=p

```

Input goes like

```
[0.3 0.4 0.3] 4

```

Explanation:

```
q~:S                                 "Read and parse the input, store sum in S";
    f*:L                             "Do S.W, store the dot product in L";
         S),                         "Get array of 0 to S";
        ,   a*                       "Create an array with N copies of the above array";
              {m*{(+}%}*             "Get all possible N length combinations of 0 to S ints";
                        {1bS=},      "Filter to get only those which sum up to S";
{L]z::-Yf#:+}$                       "Sort them based on (S.W_i - L_i)^2 value";
 L                                   "Put the dot product after the sum combination";
  ]z                                 "Wrap in an array and transpose";
    ::-                              "For each row, get difference, i.e. S.W_i - L_i";
       Yf#                           "Square every element";
          :+                         "Take sum";
              0=p                    "After sorting on sum((S.W_i - L_i)^2), take the";
                                     "first element, i.e. smallest sum and print it";

```

Try it online here
> 2 votes

# Answer
# Pyth: 40 bytes

```
Mhosm^-*Ghded2C,HNfqsTGmms+*G@Hb}bklHyUH

```

This defines a function `g` with 2 parameters. You can call it like `Mhosm^-*Ghded2C,HNfqsTGmms+*G@Hb}bklHyUHg5 [0.1 0.2 0.3 0.4`.

Try it online: Pyth Compiler/Executor

## Explanation:

```
mms+*G@Hb}bklHyUH     (G is S, H is the list of weights)
m             yUH    map each subset k of [0, 1, ..., len(H)-1] to:
 m          lH          map each element b of [0, 1, ..., len(H)-1] to:
    *G@Hb                  G*H[b]
   +     }bk               + b in k
  s                       floor(_)

```

This creates all possible solutions `L`, where `L[i] = floor(S*W[i])` or `L[i] = floor(S*W[i]+1)`. For instance, the input `4 [0.3 0.4 0.3` creates `[[1, 1, 1], [2, 1, 1], [1, 2, 1], [1, 1, 2], [2, 2, 1], [2, 1, 2], [1, 2, 2], [2, 2, 2]]`.

```
fqsTG...
f    ... only use the solutions, where
 qsTG       sum(solution) == G

```

Only `[[2, 1, 1], [1, 2, 1], [1, 1, 2]]` remain.

```
Mhosm^-*Ghded2C,HN
  o                  order the solutions by
   s                   the sum of
    m         C,HN       map each element d of zip(H, solution) to
     ^-*Ghded2           (G*d[0] - d[1])^2
 h                   use the first element (minimum)
M                    define a function g(G,H): return _

```
> 2 votes

# Answer
# Mathematica 108

```
s_~f~w_:=Sort[{Tr[(s*w-#)^2],#}&/@
Flatten[Permutations/@IntegerPartitions[s,{Length@w},0~Range~s],1]][[1,2]]

```

---

```
f[3, {0, 1, 0}]
f[4, {0.3, 0.4, 0.3}]
f[5, {0.3, 0.4, 0.3}]
f[21, {0.3, 0.2, 0.5}]
f[5, {0.1, 0.2, 0.3, 0.4}]

```

> {0, 3, 0}
> {1, 2, 1}
> {1, 2, 2}
> {6, 4, 11}
> {0, 1, 2, 2}

---

## Explanation

Ungolfed

```
f[s_,w_]:=
Module[{partitions},
partitions=Flatten[Permutations/@IntegerPartitions[s,{Length[w]},Range[0,s]],1];
Sort[{Tr[(s *w-#)^2],#}&/@partitions][[1,2]]]

```

`IntegerPartitions[s,{Length@w},0~Range~s]` returns all the integer partitions of `s`, using elements taken from the set `{0, 1, 2, ...s}` with the constraint that the output should contain the same number of elements as in the set of weights, `w`.

`Permutations` gives all of the ordered arrangements of each integer partition.

`{Tr[(s *w-#)^2],#}` returns a list of ordered pairs, `{error, permutation}` for each permutation.

`Sort[...]` sorts the list of `{{error1, permutation1},{error2, permutation2}...according to the size of the error.`

`[[1,2]]]` or `Part[<list>,{1,2}]` returns the second item of the first element in the sorted list of `{{error, permutation}...}`. In other words, it returns the permutation with the smallest error.
> 2 votes

# Answer
# R, ~~85~~ ~~80~~ 76

Uses the Hare Quota method.

Removed a couple after seeing the spec that **W** will sum to 1

```
function(a,b){s=floor(d<-b*a);s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s}

```

Test run

```
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(3,c(0,1,0))
[1] 0 3 0
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(1,c(0.4,0.3,0.3))
[1] 1 0 0
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(4,c(0.3, 0.4, 0.3))
[1] 1 2 1
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(5,c(0.3, 0.4, 0.3))
[1] 1 2 2
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(21,c(0.3, 0.2, 0.5))
[1]  6  4 11
> (function(a,b){s=floor(d<-b/(sum(b)/a));s[o]=s[o<-rev(order(d%%1))[0:(a-sum(s))]]+1;s})(5,c(0.1,0.2,0.3,0.4))
[1] 1 1 1 2
>

```
> 2 votes

# Answer
# Octave, ~~87~~ 76

Golfed:

```
function r=w(s,w)r=0*w;for(i=1:s)[m,x]=max(s*w-r);r(x)+=1;endfor endfunction

```

Ungolfed:

```
function r=w(s,w)
  r=0*w;   # will be the output
  for(i=1:s)
    [m,x]=max(s*w-r);
    r(x)+=1;
  endfor
endfunction

```

(Blasted "endfor" and "endfunction"! I'll never win but I do enjoy golfing with a "real" language.)
> 2 votes

# Answer
# Python, ~~139~~ ~~128~~ 117 bytes

```
def f(S,W):
 L=(S+1,0,[]),
 for n in W:L=[(x-i,y+(S*n-i)**2,z+[i])for x,y,z in L for i in range(x)]
 return min(L)[2]

```

## Previous itertools solution, 139 bytes

```
from itertools import*
f=lambda S,W:min((sum(x)!=S,sum((S*a-b)**2for a,b in zip(W,x)),list(x))for x in product(*tee(range(S+1),len(W))))[2]

```
> 2 votes

# Answer
# T-SQL, ~~167~~ 265

Because I like to try and do these challenges in a query as well.

Turned it into an inline function to better fit the spec and created a type for the table data. It cost a bit, but this was never going to be a contender. Each statement needs to be run separately.

```
CREATE TYPE T AS TABLE(A INT IDENTITY, W NUMERIC(9,8))
CREATE FUNCTION W(@ int,@T T READONLY)RETURNS TABLE RETURN SELECT CASE WHEN i<=@-SUM(g)OVER(ORDER BY(SELECT\))THEN g+1 ELSE g END R,A FROM(SELECT A,ROW_NUMBER()OVER(ORDER BY (W*@)%1 DESC)i,FLOOR(W*@)g FROM @T)a

```

In use

```
DECLARE @ INT = 21
DECLARE @T T
INSERT INTO @T(W)VALUES(0.3),(0.2),(0.5)
SELECT R FROM dbo.W(@,@T) ORDER BY A

R
---------------------------------------
6
4
11

```
> 1 votes

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


title: Self replicating Hello World program

text:
# Question
Title: Self replicating Hello World program
Create a self-replicating Hello World Program. (The program has the ability to use the compiler, if you want).

For example:

```
void main()
{
    printf("Hello, World!");
    DuplicateFile("main.exe", "main2.exe");
}

```

---

**Alternate challenge:** A "quine" Hello World Program.

# Answer
## Bash - 43

```
echo $(echo Hello, World! >&2)$BASH_COMMAND

```

This prints "Hello, World!" on standard error, and itself on standard output.

For fun:

```
$ ./replicate-hello.bash
Hello, World!
echo $(echo Hello, World! >&2)$BASH_COMMAND
$ ./replicate-hello.bash | bash
Hello, World!
Hello, World!
echo $(echo Hello, World! >&2)$BASH_COMMAND
$ ./replicate-hello.bash | bash | bash
Hello, World!
Hello, World!
Hello, World!
echo $(echo Hello, World! >&2)$BASH_COMMAND
$ bash <<< $(echo ./replicate-hello.bash; \
             for ((i=0;i<100;i++)) ; do echo "| bash"; done)
Hello, World!
Hello, World!
Hello, World!
Hello, World!
... snip ...
Hello, World!
Hello, World!
Hello, World!
echo $(echo Hello, World! >&2)$BASH_COMMAND

```
> 13 votes

# Answer
## PHP, 13

```
Hello, world!

```

The only way to have a program that prints both "Hello, world!" and itself is this.

Edit: note that the question was not quite as clear when I wrote this.
> 4 votes

# Answer
## Windows Batch file

```
@echo Hello World
@copy "%~dpnx0" "%~dpn02%~x0" >nul 2>&1

```
> 4 votes

# Answer
# Erlang 1342 chars, 3 lines

Not sure if I've understood the question correctly here, I ended up writing a quine that writes to another file...

```
-module(hi).
-export([h/0]).
h()->io:fwrite("Hello World!"),P=[45,109,111,100,117,108,101,40,104,105,41,46,10,45,101,120,112,111,114,116,40,91,104,47,48,93,41,46,10,104,40,41,45,62,105,111,58,102,119,114,105,116,101,40,34,72,101,108,108,111,32,87,111,114,108,100,33,34,41,44,80,61],Q=[44,102,105,108,101,58,119,114,105,116,101,95,102,105,108,101,40,34,104,105,50,46,101,114,108,34,44,80,41,44,102,105,108,101,58,119,114,105,116,101,95,102,105,108,101,40,34,104,105,50,46,101,114,108,34,44,105,111,95,108,105,98,58,102,119,114,105,116,101,40,34,126,119,34,44,91,80,93,41,44,91,97,112,112,101,110,100,93,41,44,102,105,108,101,58,119,114,105,116,101,95,102,105,108,101,40,34,104,105,50,46,101,114,108,34,44,32,34,44,81,61,34,44,91,97,112,112,101,110,100,93,41,44,102,105,108,101,58,119,114,105,116,101,95,102,105,108,101,40,34,104,105,50,46,101,114,108,34,44,105,111,95,108,105,98,58,102,119,114,105,116,101,40,34,126,119,34,44,91,81,93,41,44,91,97,112,112,101,110,100,93,41,44,102,105,108,101,58,119,114,105,116,101,95,102,105,108,101,40,34,104,105,50,46,101,114,108,34,44,81,44,91,97,112,112,101,110,100,93,41,46],file:write_file("hi2.erl",P),file:write_file("hi2.erl",io_lib:fwrite("~w",[P]),[append]),file:write_file("hi2.erl", ",Q=",[append]),file:write_file("hi2.erl",io_lib:fwrite("~w",[Q]),[append]),file:write_file("hi2.erl",Q,[append]).

```

I'm currently learning Erlang, so it was a good learning experience anyway.
> 3 votes

# Answer
# Javascript, 89 bytes

I'm not quite sure if this is what you're asking, but this program has "hello world" in it and outputs itself.

```
//hello world
var f=function (){return "//hello world\nvar f="+f.toString()+";f();"};f();

```
> 1 votes

# Answer
# Java (1045)

I've done this before.

```
import java.io.*;
import javax.tools.*;
class H1 {
  static final char Q=34;
  static final int N=1;
  public static void main(String[]a)throws Exception{
    String fn="H"+(N+1)+".java";
    BufferedWriter out=new BufferedWriter(new FileWriter(fn));
    String s="import java.io.*;import javax.tools.*;class H%d{static final char Q=34;static final int N=%d;public static void main(String[]a)throws Exception{String fn=%cH%c+(N-1)+%c.java%c;BufferedWriter out=new BufferedWriter(new FileWriter(fn));String s=%c%s%c;out.write(String.format(s,N+1,N+1,Q,Q,Q,Q,Q,s,Q,Q,Q,Q,Q));out.close();JavaCompiler c=ToolProvider.getSystemJavaCompiler();c.run(null,null,null,fn);Class.forName(%cH%c+(N+1)).getMethod(%cmain%c,a.getClass()).invoke(null,new Object[]{new String[]{}});}}";
    out.write(String.format(s,N+1,N+1,Q,Q,Q,Q,Q,s,Q,Q,Q,Q,Q));
    out.close();
    JavaCompiler c=ToolProvider.getSystemJavaCompiler();
    c.run(null,null,null,fn);
    Class.forName("H"+(N+1)).getMethod("main",a.getClass()).invoke(null,new Object[]{new String[]{}});
  }
}

```

It floods the directory with `H*.java` and `H*.class` files. It somehow stops by itself with a huge stack trace after 500 compilations. I don't know how to fix that problem.

Here is what a flooded desktop looks like:

https://www.dropbox.com/s/iy8ggzps7s55z4e/java2.png?dl=0 https://www.dropbox.com/s/jrauw3igjiwrpmd/java1.png?dl=0
> 1 votes

---
Tags: code-golf
---


title: Score a game of Go

text:
# Question
Title: Score a game of Go
Scoring a Go game is a task that is not all too easy. In the past there have been several debates about how to design rules to cover all the strange corner cases that may occur. Luckily, in this task you don't have to do complicated stuff like life and death or seki detection. In this task, you have to implement a program that scores a game according to the Tromp-Taylor rules without Komi.
The scoring procedure is pretty simple:

> a point P, not colored C, is said to reach C, if there is a path of (vertically or horizontally) adjacent points of P's color from P to a point of color C.
> A player's score is the number of points of her color, plus the number of empty points that reach only her color.

For example, consider the following board. `X`, `O` and `-` denote black, white and uncoloured intersections:

```
- - - X - O - - -
- - - X - O - - -
- - - X - O - - -
- - - X O - - O -
X X X O - O O - -
- - - X O - - O O
- - - X - O - - -
- - - X - O - X -
- - - - - O - - -

```

Applying the scoring rule yields the following result. `x`, `o` and `-` represent uncoloured intersections that are counted as black, white and nobody's points.

```
x x x X - O o o o
x x x X - O o o o
x x x X - O o o o
x x x X O o o O o
X X X O o O O o o
- - - X O - - O O
- - - X - O - - -
- - - X - O - X -
- - - - - O - - -

```

According to the diagram, black has 23 points, white has 29 points of territory. Thus, your program should print `W+6` for this board.

I hope it is clear enough this way.

## Input and output

The input is a string that contains exactly  of the characters `X`, `O`, `-` where *n* is not known at compile time. Your program should ignore all other characters in the input stream. Behavior is undefined if there is no integer *n* such that the amount of `XO-` characters equals . You may assume that *n* is in *\[0, 255\]*.

The sequence of characters is to be interpreted as a Go-board of *n* rows and columns. The output is the absolute value of the difference of the total amount of points of white and black in decimal representation. If white has more points, it is prefixed by `W+`, if black has more points it is prefixed by `B+`. In the case that both players have an equal amount of points, the output is `Jigo`.

Input is to be read in an implementation defined manner. Input may not be part of the source code.

## Winning conditions

This is code-golf. Usual code-golf conventions apply. The submission with the least amount of characters in its source wins. Only programs that fully implement the specification may win.

## Test cases

Input:

```
- - - X - O - - -
- - - X - O - - -
- - - X - O - - -
- - - X O - - O -
X X X O - O O - -
- - - X O - - O O
- - - X - O - - -
- - - X - O - X -
- - - - - O - - -

```

Output: `W+6`

Input:

```
Xavier is insane -- says Oliver

```

Output: `Jigo`

Inpout:

```
Code-Golf

```

Output: `Jigo`

Input:

```
-XXXXXXX-XOOOOOOOXXO-OXXXOXXXOX--XOXXOOX
-
XOOXXOX--XOXXXOXXXO-OXXOOOOOOOX-XXXXXXX-

```

Output: `B+21`

Input:

```
- - X O O O O X X - - - - - - X O O -
- X X O X O X X O X X X X X X - X O -
- X O O X X X - O O O X O O X X X O -
- X O O O X X O O O O O O X X X O - -
- - X X O X - X X X X O O O O O O O -
- - X O O X X X - X X X O O O X X O -
- - X O - O X O X O O O O O X X X O -
- X O O - O O O X X X X X O O X O - -
- X X X O - - - O X O X X X O X O - -
X O O O O - - O - O O O O X X X O O -
X X O - - - O - - O O X X - - X X O O
X O O O - - O - O O X - - - - X O O X
- X X X O O X O O X X - - - - X X X X
X - X X X O X X O O X - - X X O X O O
X X O O X O X O X X - - - X O O O O -
X O - O X X X O X - - - - - X O - - -
O O - O X O O O O X X - X X X X O - -
O O - O O O X O X X - - X - X X O - -
- - O - - O X X X - - - - X O O O - -

```

Output: `B+6`

More testcases will come soon.

## reference implementation

I have created a reference implementation written in ANSI C. This implementation reads input from the standard input and writes output to the standard output.

```
/* http://codegolf.stackexchange.com/q/6693/134
 * reference implementation
 * by user FUZxxl
 */

#include <stdio.h>
#include <stdlib.h>

#define MAXBOARD 256

/* bit 0x01: black colour
 * bit 0x02: white colour
 * bit 0x04: there is a stone on the intersection
 */

enum colour {
    UNCOLOURED    = 0x0,
    BLACK_REACHED = 0x1,
    WHITE_REACHED = 0x2,
    BOTH_REACHED  = 0x3,
    HAS_STONE     = 0x4,
    BLACK         = 0x5,
    WHITE         = 0x6
};

static enum colour board[MAXBOARD * MAXBOARD] = { 0 };

static int bsize = 0;

static void read_input(void);
static void fill_board(void);
static void show_score(void);

int main()
{
    read_input();
    fill_board();
    show_score();
    return EXIT_SUCCESS;
}

static void read_input(void)
{
    int n = 0;
    int invalue;

    while ((invalue = getchar()) != EOF) {
        switch (invalue) {
            case '-': board[n++] = UNCOLOURED; break;
            case 'X': board[n++] = BLACK; break;
            case 'O': board[n++] = WHITE; break;
        }
    }

    while (bsize * bsize < n) bsize++;

    /* your program may exhibit undefined behaviour if this is true */
    if (bsize * bsize != n) exit(EXIT_FAILURE);
}

static void fill_board(void)
{
    int i,j;
    int changes;
    enum colour here, top, bottom, left, right, accum;

    do {
        changes = 0;

        for (i = 0; i < bsize; ++i) {
            for (j = 0; j < bsize; ++j) {

                here   = board[i * bsize + j];
                if (here >= BOTH_REACHED) continue;

                top    = i == 0 ? UNCOLOURED : board[(i - 1) * bsize + j];
                left   = j == 0 ? UNCOLOURED : board[i * bsize + j - 1];
                bottom = i == bsize-1 ? UNCOLOURED : board[(i + 1) * bsize + j];
                right  = j == bsize-1 ? UNCOLOURED : board[i * bsize + j + 1];

                accum = here | top | bottom | left | right;
                accum &= ~HAS_STONE;

                changes |= board[i * bsize + j] != accum;

                board[i * bsize + j] = accum;

            }
        }

    } while (changes);
}

static void show_score(void) {
    int w = 0, b = 0, n;

    for (n = 0; n < bsize*bsize; ++n) switch (board[n] & ~HAS_STONE) {
        case BLACK_REACHED: ++b; break;
        case WHITE_REACHED: ++w; break;
    }

    if (b != w)
        printf("%s%i\n",b>w?"B+":"W+",abs(b-w));
    else
        printf("Jigo\n");
}

```

# Answer
> 3 votes
## GolfScript (105 bytes)

```
{'-XO'?}/]-1-.{2*3%}%{.,:N),{.*N=}?/{{[{.2$+1={+.}*}*]}%zip}N*[]*.1--,\}2*-.{.0>'W+B+'2/=\abs}{;'Jigo'}if

```

Online demo.

Flood-fill adapted from this earlier answer of mine.

The solution flood-fills one copy of the original board with X, and another with O. Thus empty cells which are reachable by both colours are scored for both, but cancel in the subtraction.

# Answer
> 6 votes
# C (~~438~~ ~~434~~ ~~413~~ ~~382~~ ~~364~~ ~~336~~ ~~322~~ ~~298~~ ~~294~~ ~~292~~ 290 characters)

```
#define I b[d*g+e
a;b[65536];c;d;e;f;g;main(){for(;d=getchar()+1;f++)b[f]=d-80?d-89?d-46&&
f--:5:6,g+=g*g<f;while(!c--)for(d=g;d--;)for(e=g;e--;)I]<3?a=3&(I]|!!d*I
-g]|!!e*I-1]|(d<g-1)*I+g]|(e<g-1)*I+1]),c&=I]==a,I]=a:0;while(f--)c+=b[f
]%2-b[f]/2%2;printf(c?"%c+%i":"Jigo",c>0?66:87,abs(c));}

```

All newlines except the first one inserted for enhanced legibility. A commented and slightly more legible version can be found here.

This answer is essentially the reference solution but with all that useless stuff (such as types \[who needs something different from `int` anyway?\] and standards compliance \[return value of main? please!\])

## Corrections and improvements

### 438 → 434

Dropped explicit initialization of variables after I convinced myself that they are automatically initialized to `0` according to standard.

### 434 → 413

Removed case statement: If an uncoloured intersection is reachable from both black and white, we can count it as one point for both to simplify the program. Switch of logical branches to avoid negation.

### 413 → 382

Assign `d` to `getchar()+1` to save one pair of parenthesis. Under the assumption that `b` is initialized to zeroes, reorder `case` statements, discarding all `break` statements. `(a>b?c:0)` is longer than `(a>b)*c`. `(d+1)*g+e` is longer than `d*g+e+g`.

### 382 → 364

Improved looping, no newlines in the output, shorter output routines.

### 364 → 336

Got rid of that `switch` statement. (Thanks, Howard!), track difference of points for two characters. Negate `c` for one character. four characters in the big or clause.

### 336 → 323

Replacing `&` by `%` allows removal of braces for four characters. Fused the square-root with the input loop for nine or so characters (yeah!), removed an `if` for one char.

### 323 → 298

Introduced the macro `H` to replace the often occuring and bulky `b[d*g+e]` construct.

### 298 → 294

Change `a&=~4` to `a&=3` as we only every observe the lowest three bytes of `a`. Also changed to loop body from `((a=I])<3)?a|=...` to `I]<3?a=I]|...` which is two characters shorter. Also, introduce `h` instead of reusing `c`, which is one character shorter.

### 294 → 292

Eliminate `h` variable. If we test `c` with `!c--` instead of `!c++`, `c` equals 0 at the end of the flood-fill loop and can thus be used for the purpose `h` was used before (i.e. score keeping).

### 292 → 290

Replace the construct `d-46?f--:0` with `d-46&&f--` which is shorter by a character and combine the two assignments to `a` in the inner loop.

# Answer
> 6 votes
## J (~~140~~ ~~136~~ ~~131~~ ~~129~~ ~~119~~ ~~117~~ 116 characters)

After ramping up my J skills, I can finally provide a submission in J. It's a little bit long though.

```
exit echo>(*{'Jigo';('B+',":);'W+',":@|)+/,-/1 2=/(]OR(0=[)*[:OR((,.|.)0,i:1)|.!.0])^:_~($~,~@%:@#)3-.~'-XO'i:1!:1]3

```

The algorithm implemented by this submission is very similar to the reference implementation but different in the way occupied fields are handled.

Here is the solution split up into more parts for easier understandability. The golfed solution is slightly different from that, but the difference isn't very large.

```
input =. 3 -.~ '-XO' i: 1!:1 ] 3
board =. ($~ ,~@%:@#) input
NB. shift up, down, left, right
rotm =. (,. |.) 0 , i: 1
fill =. ] OR (0 = [) * [: OR rotm |.!.0 ]
filledboard =. fill^:_~ board
score =. +/ , -/ 1 2 =/ filledboard
echo > (* { 'Jigo' ; ('B+' , ":) ; ('W+', ":@|)) score
exit 0

```

# Answer
> 5 votes
### GolfScript, 190 characters

```
{"XO-"?)},:v,.),\{\.*=}+,~:s.*:`0\,{s%!\2*+}/:r;88{0v@{=\2*+}+/}:%~79%1${{:<.r|r^2*|<2/r|r^|<2s?:h/|<h*|1$|1$^2`?(&}`*}:a~@@a\;.2$|2${^2*)2base{+}*}:m~@2$|@m-.{"BW"1/1$0>="+"@abs}{;"Jigo"}if

```

The script became much longer than I thought in the beginning. Pass any input on STDIN and the output will then be printed when the program terminates.

# Answer
> 2 votes
# Ruby (314)

could be made shorter with some more time:

```
q={?-=>0,?X=>5,?O=>6};b=[];$<.chars{|c|(t=q[c])&&b<<t}
z=Math.sqrt b.size
loop{c=b.each_with_index.map{|h,i|
next h if h>2
x=i%z
y=i/z
u=y<1?0:b[i-z]
l=x<1?0:b[i-1]
d=y>z-2?0:b[i+z]
r=x>z-2?0:b[i+1]
~4&(h|u|d|l|r)}
break if c==b
b=c}
b.map!{|h|h&~4}
s=b.count(1)-b.count(2)
puts s==0?"Jigo":s>0?"B+#{s}":"W+#{-s}"

```

---
Tags: code-golf, game, graph-theory, board-game, go
---


# Question
Title: Shortest code to throw IllegalArgumentException in Java
Okey, we all know the normal way to throw a IllegalArgumentException in Java:

```
throw new IllegalArgumentException(); // 37 characters

```

But there must be a shorter (as in less characters) ways to do so. How can we produce a java.lang.IllegalArgumentException with even less code?

* The code fragment has to compile and run in java 7.
* No imports/external packages (e.g. not using `java.util.Arrays.toString()` )
    + only exception: java.lang because it is automatically imported.
* You can add own methods/classes.
* It must throw a java.lang.IllegalArgumentException
    + **Edit:** the error output (stacktrace) must name it java.lang.IllegalArgumentException, so no subclasses of it.

To have a base to start from:

```
class Titled {
    public static void main(String[] args) {
        throw new IllegalArgumentException();
    }
}

```

# Answer
These were all found by `grep`ping the source code in the package `java.lang`.

All of them result in a "pure" `IllegalArgumentException` (i.e. not a subclass of it).

The ones marked `*` only work if you add `" throws Exception"` (18 characters) to your `main` declaration, as they throw a checked exception of some kind.

## 12 (30?) characters\*

```
"".wait(-1);

```

This will result in:

```
java.lang.IllegalArgumentException: timeout value is negative

```

## 22 (40?) characters\*

```
new Thread().join(-1);

```

## 22 characters

```
Character.toChars(-1);

```

## 30 characters

```
Character.UnicodeBlock.of(-1);

```
> 29 votes

# Answer
Here's a nice short way to do it, in **~~17~~ 13 chars**:

```
new Long("");

```

It throws a `NumberFormatException`, which is an `IllegalArgumentException`. This and this verify it.

Equivalently, one could do

```
new Byte("");

```
> 23 votes

# Answer
# 22 characters:

```
Character.toChars(-1);

```

Running example
Javadoc: java.lang.Character.toChars(int)

**Some nice looking variants:**

```
Character.toChars(~4); // 22 characters, number can be any non-negative (and -0)

```

```
Character.toChars(1<<7); // 24 characters

```

`~i` is the same as `-1 * (i+1)` because it inverts the bits. So we will get a illegal parameter, because it is smaller then 0.
`1<<7` will create a too high number by shifting the 1 seven times. (same as multiply it 7 times with 2). The last accepted Value seems to be `1114111`, `1114112` will fail. *Note:* this might change depending on your environment, and could be not always reliable.

See the Oracle Docs "Bitwise and Bit Shift Operators" and "Primitive Data Types"

# 28 characters:

And if you don't like using the character class in a character count competition\*:

```
Enum.valueOf(Enum.class,""); // 28 characters

```

*\*) Just to make this pun.*
> 10 votes

# Answer
# 21 characters:

```
System.getProperty("");

```

As per the documentation, `getProperty` and `setProperty` throw `IllegalArgumentException` if the key is empty.
> 8 votes

# Answer
# 25 Characters

Creates a vector with an invalid (negative) length:

```
new java.util.Vector(-1);

```

Displays:

```
Exception in thread "main" java.lang.IllegalArgumentException: Illegal Capacity: -1
    at java.util.Vector.<init>(Vector.java:129)
    at java.util.Vector.<init>(Vector.java:144)
    at Titled.main(Titled.java:3)

```
> 5 votes

# Answer
Here's 24 characters:

```
System.out.printf("%z");

```

This will throw an `IllegalFormatException`, which is an `IllegalArgumentException`.
> 1 votes

# Answer
# 19 characters:

```
String.format("%");

```

Throws `java.util.UnknownFormatConversionException`, which inherits from `IllegalFormatException`, which, in turn, inherits from `IllegalArgumentException`;
> 1 votes

# Answer
# **14 Characters**

```
this.wait(-1);

```

# **17 Characters**

```
Thread.sleep(-1);

```

As far as code that directly throws IllegalArgumentException, these will do it.

```
From documentation:
Thread.sleep(int millis):
Throws:IllegalArgumentException - if the value of millis is negative
InterruptedException - if any thread has interrupted the current thread.

```

so direct code is 17 chars, if you're being a super stickler and counting the chars to add a throws clause for the interupted exception you can shorten it by just throwing the raw Exception class
> 1 votes

---
Tags: code-golf, java
---


title: Key length of Vigenère cipher

text:
# Question
Title: Key length of Vigenère cipher
The Vigenère cipher is a substitution cipher where the encryption of each letter of the plaintext depends on a different character in a keyword. This stops you using simple methods of frequency analysis to guess the correct substitution. However, the keyword is repeated if it is shorter than the plaintext. This is a weakness. If the length of the keyword is known (n, say), however, and is much shorter than the message, then you can decompose the message into separate sections by taking every nth letter. You can then use frequency analysis on these.

The Kasiski examination is a method to work out the most likely key lengths. It does this by considering identical substrings which happen to be a multiple of the key length apart. They are therefore encrypted in the same way. Turning this round, identical substrings in the ciphertext are likely to be a multiple of the key length apart. If you identify these distances, then the key length is likely to be a common factor of all these distances.

Your job is to write a function or program that can guess the most likely length of the keyword, given some encrypted text. To be precise, the function or program (just called function below) will satisfy the following:

* Inputs consist of a string representing the ciphertext and a positive integer (**len**, for the purposes of this spec) representing the shortest common substring to look at.
* The ciphertext will consist of upper case A-Z characters only. Any length is permitted.
* You can assume valid inputs without checking.
* The inputs may be passed in, or read from stdin.
* The function will identify all pairs of identical substrings in the ciphertext which have a length of *at least* **len**.
* Substrings in each pair may not overlap but substrings in different pairs can overlap.
* The function will return, or write to stdout, the highest common factor of the distances between the starts of these identical pairs.
* If there are no identical substrings then the function will return 0.

For example:

"AAAAAAAAAAAAAAAAAA", n returns 1 for any n from 1 to 8, 9 for n = 9 (as the only possible non-overlapping substrings of length 9 happen to be the same) and 0 otherwise.

"ABCDEFGHIJKL", n returns 0 for any n

"ABCDEABCDE", n returns 5 for n\<=5 and 0 otherwise

"ABCABABCAB", 2 returns 1 because "AB" pairs are separated by 2,3,5 & 8

"ABCABABCAB", 3 returns 5

"**VHVS**SP*QUCE*MRVBVBBB**VHVS**URQGIBDUGRNICJ*QUCE*RVUAXSSR", 4 returns 6 because the repeating "VHVS" are 18 characters apart, while "QUCE" is separated by 30 characters

Naturally, lowest byte count wins and avoid standard loopholes.

# Answer
> 2 votes
# CJam, 67 bytes

Definitely still room for improvement, but I'll post what I have so far.

Try it online

```
0r:T,,ri>{T,L(-,_m*{~:XT>L<T@LX+e>,{0t}/X>\#_W>\2$?{\1$_!+%}h;}/}fL

```

# Answer
> 1 votes
# JavaScript (ES6) 117

```
F=(s,n,G=(a,b)=>b?G(b,a%b):a)=>(i=>{
  for(f=i;s[(j=i+n)-1];i++)
    for(;p=~s.indexOf(s.substr(i,n),j++);)
      f=G(~p-i,f)
})(0)|f

```

**Ungolfed**

```
F=(s,n)=>
{
  var G = (a,b) => b ? G(b,a%b) : a; // GCD function
  var p,w,i,j, f = 0; // f starting divisor
  for(i = 0; s[i + n - 1]; ++i) // scan s for each substring of lenght n
  {
     w = s.substr(i,n);
     for (j=i+n; (p = s.indexOf(w,j)) != -1; ++j) // find all occurrencies of substring in the rest f the string
        f = G(p - i, f); // p-i is the distance between pairs
  }
  return f
}

```

**Test** In Firefox/FireBug console

```
;["AAAAAAAAAAAAAAAAAA","ABCDEFGHIJKL","ABCDEABCDE","ABCABABCAB",
  "VHVSSPQUCEMRVBVBBBVHVSURQGIBDUGRNICJQUCERVUAXSSR"]
.forEach(s=>{
  for(o=[],i=1;i<=10;i++) o.push(i+':'+F(s,i));
  console.log(s+' '+o)
})

```

*Output*

```
AAAAAAAAAAAAAAAAAA 1:1,2:1,3:1,4:1,5:1,6:1,7:1,8:1,9:9,10:0
ABCDEFGHIJKL 1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0,10:0
ABCDEABCDE 1:5,2:5,3:5,4:5,5:5,6:0,7:0,8:0,9:0,10:0
ABCABABCAB 1:1,2:1,3:5,4:5,5:5,6:0,7:0,8:0,9:0,10:0
VHVSSPQUCEMRVBVBBBVHVSURQGIBDUGRNICJQUCERVUAXSSR 1:1,2:1,3:6,4:6,5:0,6:0,7:0,8:0,9:0,10:0

```

---
Tags: code-golf, cryptography
---


title: Iterated Divisor Twist

text:
# Question
Title: Iterated Divisor Twist
# Definitions

Let `m` and `n` be positive integers. We say that `m` is a *divisor twist* of `n` if there exists integers `1 < a ≤ b` such that `n = a*b` and `m = (a - 1)*(b + 1) + 1`. If `m` can be obtained from `n` by applying zero or more divisor twists to it, then `m` is a *descendant* of `n`. Note that every number is its own descendant.

For example, consider `n = 16`. We can choose `a = 2` and `b = 8`, since `2*8 = 16`. Then

```
(a - 1)*(b + 1) + 1 = 1*9 + 1 = 10

```

which shows that `10` is a divisor twist of `16`. With `a = 2` and `b = 5`, we then see that `7` is a divisor twist of `10`. Thus `7` is a descendant of `16`.

# The task

Given a positive integer `n`, compute the descendants of `n`, listed in increasing order, without duplicates.

# Rules

You are not allowed to use built-in operations that compute the divisors of a number.

Both full programs and functions are accepted, and returning a collection datatype (like a set of some kind) is allowed, as long as it is sorted and duplicate-free. The lowest byte count wins, and standard loopholes are disallowed.

# Test Cases

```
1 ->  [1]
2 ->  [2] (any prime number returns just itself)
4 ->  [4]
16 -> [7, 10, 16]
28 -> [7, 10, 16, 25, 28]
51 -> [37, 51]
60 -> [7, 10, 11, 13, 15, 16, 17, 18, 23, 25, 28, 29, 30, 32, 43, 46, 49, 53, 55, 56, 60]

```

# Answer
# Python 2, ~~109~~ ~~98~~ ~~85~~ 82 bytes

```
f=lambda n:sorted(set(sum(map(f,{n-x+n/x for x in range(2,n)if(n<x*x)>n%x}),[n])))

```

Since `(a-1)*(b+1)+1 == a*b-(b-a)` and `b >= a`, descendants are always less than or equal to the original number. So we can just start with the initial number and keep generating strictly smaller descendants until there are none left.

The condition `(n<x*x)>n%x` checks two things in one - that `n<x*x` and `n%x == 0`.

*(Thanks to @xnor for taking 3 bytes off the base case)*

# Pyth, 32 bytes

```
LS{s+]]bmydm+-bk/bkf><b*TT%bTr2b

```

Direct translation of the above, except for the fact that Pyth seems to choke when trying to sum (`s`) on an empty list.

This defines a function `y` which can be called by appending `y<number>` at the end, like so (try it online):

```
LS{s+]]bmydm+-bk/bkf><b*TT%bTr2by60

```

# CJam, ~~47~~ 45 bytes

```
{{:X_,2>{__*X>X@%>},{_X\/\-X+}%{F}%~}:F~]_&$}

```

Also using the same method, with a few modifications. I wanted to try CJam for comparison, but unfortunately I'm much worse at CJam than I am at Pyth/Python, so there's probably a lot of room for improvement.

The above is a block (basically CJam's version of unnamed functions) that takes in an int and returns a list. You can test it like so (try it online):

```
{{:X_,2>{__*X>X@%>},{_X\/\-X+}%{F}%~}:F~]_&$}:G; 60 Gp

```
> 9 votes

# Answer
# Java, 148 146 104 bytes

Golfed version:

```
import java.util.*;Set s=new TreeSet();void f(int n){s.add(n);for(int a=1;++a*a<n;)if(n%a<1)f(n+a-n/a);}

```

Long version:

```
import java.util.*;
Set s = new TreeSet();
void f(int n) {
    s.add(n);
    for (int a = 1; ++a*a < n;)
        if (n%a < 1)
            f(n + a - n/a);
}

```

So I'm making my debut on PPCG with this program, which uses a `TreeSet` (which automatically sorts the numbers, thankfully) and recursion similar to Geobits' program, but in a different manner, checking for multiples of *n* and then using them in the next function. I'd say this is a pretty fair score for a first-timer (especially with Java, which doesn't seem to be the most ideal language for this kind of thing, and Geobits' help).
> 6 votes

# Answer
# Java, ~~157~~ 121

Here's a recursive function that gets descendants of each descendant of `n`. It returns a `TreeSet`, which is sorted by default.

```
import java.util.*;Set t(int n){Set o=new TreeSet();for(int i=1;++i*i<n;)o.addAll(n%i<1?t(n+i-n/i):o);o.add(n);return o;}

```

With some line breaks:

```
import java.util.*;
Set t(int n){
    Set o=new TreeSet();
    for(int i=1;++i*i<n;)
        o.addAll(n%i<1?t(n+i-n/i):o);
    o.add(n);
    return o;
}

```
> 4 votes

# Answer
# Octave, ~~107~~ 96

```
function r=d(n)r=[n];a=find(!mod(n,2:sqrt(n-1)))+1;for(m=(a+n-n./a))r=unique([d(m) r]);end;end

```

Pretty-print:

```
function r=d(n)
  r=[n];                          # include N in our list
  a=find(!mod(n,2:sqrt(n-1)))+1;  # gets a list of factors of a, up to (not including) sqrt(N)
  for(m=(a+n-n./a))               # each element of m is a twist
    r=unique([d(m) r]);           # recurse, sort, and find unique values
  end;
end

```
> 2 votes

# Answer
# Haskell, 102 100 bytes

```
import Data.List
d[]=[]
d(h:t)=h:d(t++[a*b-b+a|b<-[2..h],a<-[2..b],a*b==h])
p n=sort$nub$take n$d[n]

```

Usage: `p 16` which outputs `[7,10,16]`

The function `d` recursively calculates all descendants, but does not check for duplicates, so many appear more than once, e. g. `d [4]` returns an infinite list of `4`s. The functions `p` takes the first `n` elements from this list, removes duplicates and sorts the list. Voilà.
> 1 votes

# Answer
# CJam - 36

```
ri_a\{_{:N,2>{NNImd!\I-z*-}fI}%|}*$p

```

Try it online

Or, different method:

```
ri_a\{_{_,2f#_2$4*f-&:mq:if-~}%|}*$p

```

I wrote them almost 2 days ago, got stuck at 36, got frustrated and went to sleep without posting.
> 1 votes

---
Tags: code-golf, number-theory
---