title: A Euro-iginal Sequence

text:
# Question
Title: A Euro-iginal Sequence
Given a positive integer *n* output the *n*-th number of the euro-iginal sequence.

## Calculating the Sequence

This sequence is equal to OEIS A242491.

A number is part of said sequence if the number can be made up by using as many different euro coins or notes, but **only one of each**. Note that you don't have to consider cents.

**Example:**

`6` would be in the sequence, as it can consist of a 1-euro coin and a 5-euro-note.

`4` would NOT be in the sequence, as it can't be formed with the given requirements.

To give everyone an overview, heres a list with euro values you have to consider:

> 1€, 2€, 5€, 10€, 20€, 50€, 100€, 200€, 500€

Note that this sequence only ranges from 0 (yes, 0 is included!) to 888.

---

Here are the first 15 elements of this sequence:

0, 1, 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, ...

## Test Cases

**Input** -\> **Output**

```
2 -> 1
6 -> 6
21 -> 25
33 -> 50

```

# Answer
> 12 votes
# Jelly, 7 bytes

```
b8d4ḅ5Ḍ

```

Try it online!

### How it works

```
b8d4ḅ5Ḍ  Main link. Argument: n (integer)

b8       Convert n from integer to base 8.
  d4     Divmod each base-8 digit by 4, mapping the digit d to [d / 4, d % 4].
    ḅ5   Convert the quotient-remainder pairs from base 5 to integer, mapping
         [d / 4, d % 4] to (d / 4 * 5 + d % 4).
         The last two steps establish the following mapping for octal digits.
             0 -> [0, 0] -> 0
             1 -> [0, 1] -> 1
             2 -> [0, 2] -> 2
             3 -> [0, 3] -> 3
             4 -> [1, 0] -> 5
             5 -> [1, 1] -> 6
             6 -> [1, 2] -> 7
             7 -> [1, 3] -> 8
      Ḍ  Convert the resulting array of digits from decimal to integer.

```

# Answer
> 9 votes
# Python 2, 32 bytes

```
lambda n:n+n/4+n/32*10+n/256*100

```

Try it online!

---

# Python 2, 34 bytes

```
f=lambda n:n and 10*f(n/8)+n%8*5/4

```

Try it online!

# Answer
> 8 votes
# Husk, ~~8 7~~ 5 bytes

```
Σ!Ṗİ€

```

Try it online! **Edit:** -3 bytes thanks to Zgarb!

```
   İ€   build-in infinite sequence [1,2,5,10,20,50,100,...]
  Ṗ     power set [[],[1],[2],[1,2],[5],[1,5],[2,5],[1,2,5],...]
 !      index into the list with given input, e.g. 4 yields [1,2]
Σ       take the sum of that list

```

---

I heard that it is planned to change `İ€` to the finite sequence `[0.01,0.02,0.05,0.1,0.2,0.5,1,2,5,10,...,500]` in the future. Once that is implemented, the following code should work a byte count of 7:

```
Σ!Ṗ↓6İ€

```

where `↓6` drops the first six elements of the sequence. Try it online!

# Answer
> 6 votes
# Perl 5, 29 bytes

**28 bytes code + 1 for `-p`.**

Uses 0 based indexing.

```
$_=sprintf"%o",$_;y/4-7/5-8/

```

Try it online!

# Answer
> 5 votes
# Jelly, 11 bytes

```
0Df9,4Ṇ$$#Ṫ

```

Try it online!

Thanks a lot to @Erik the Outgolfer for a lot of help in chat!

## Explanation

```
0Df9,4Ṇ$$#Ṫ  - Monadic link.

0        #   - Collect first N matches, starting from 0.
 D           - Digits.
  f9,4       - Filter-Keep the digits that are either 9 or 4. Yields [] when there are none.
      Ṇ      - Logical NOT. [] -> 1 (truthy), non-empty list -> 0 (falsy).
          Ṫ  - Pop and return the last element.

```

# Answer
> 3 votes
# Mathematica, 47 bytes

```
(FromDigits/@0~Range~8~Drop~{5}~Tuples~3)[[#]]&

```

# Mathematica, 48 bytes

```
Sort[Tr/@Subsets@Join[x={1,2,5},10x,100x]][[#]]&

```

-6 bytes from Martin Ender

# Answer
> 3 votes
# Java 8, ~~28~~ 26 bytes

0-indexed:

```
n->n+n/4+n/32*10+n/256*100

```

Port of *@xnor*'s Python 2 answer (which used to be deleted, hence the original 1-indexed answer below).

Try it here.

---

Old 1-indexed answer (**28 bytes**):

```
n->--n+n/4+n/32*10+n/256*100

```

Port of *@Tfeld*'s Python 2 answer before he made his last edit. Instead of using `~-` a bunch of times, it uses `--n` to decrease `n` by 1 right after entering the lambda function.

Try it here.

# Answer
> 3 votes
# 05AB1E, 7 bytes

0-indexed.

Port of Mr. Xcoder's Jelly answer

```
µN7nÃg_

```

Try it online!

**Explanation**

```
µ          # loop over increasing N until input matches are found
      _    # the logical negation of
     g     # the length of
 N         # N
  7nÃ      # with only 4s and 9s kept

```

# Answer
> 2 votes
# Python 2, ~~40~~ ~~38~~ 36 bytes

Inspired by xnor's answer, but uses 1-indexing.

```
lambda n:~-n*5/4+~-n/32*10+n/257*100

```

Try it online!

# Python 2, ~~78~~ ~~65~~ ~~62~~ ~~61~~ ~~58~~ 56 bytes

```
lambda i,n=0:f(i+~-('4'in`n`or'9'in`n`),n+1)if i else~-n

```

Try it online!

# Answer
> 2 votes
# Octave, 59 bytes

```
@(n)unique((dec2bin(0:511)-48)*kron([1 2 5],10.^(0:2))')(n)

```

Try it online!

### Explanation

The code creates the full sequence and then indexes into it.

First, the binary expressions of the numbers `0`, `1`, ... `511` are generated as a 512×9 matrix:

> `dec2bin(0:511)-48`

(the `-48` part is needed because the result of `dec2bin` is characters, not numbers). This gives

```
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1
...
1 1 1 1 1 1 1 1 1

```

Then the Kronecker product of `[1 2 5]` and `[1 10 100]` is computed

> `kron([1 2 5],10.^(0:2))`

and transposed

> `'`

which gives the nine possible euro values as a 9×1 vector:

```
1
2
5
10
20
50
100
200
500

```

Matrix-multiplying the above matrix and vector

> `*`

gives a 512×1 vector containing all possible numbers in the sequence, with repetitions and unsorted:

```
  0
500
 50
...
388
888

```

Deduplicating and sorting

> `unique(...)`

gives the full sequence:

```
  0
  1
  2
...
887
888

```

Finally, the input is used to index into this sequence

> `(n)`

to produce the output.

# Answer
> 2 votes
# Jelly, 15 bytes

0-indexed.

```
æ»“£¦®‘×“¢½d‘S+

```

Try it online!

## Explanation

This is based off of xnor's Python solution, where the algorithm is **n + n/4 + n/32\*10 + n/256\*100**.

```
lambda n: sum(i * j for i, j in zip([n / i for i in [1, 4, 32, 256]], [1, 1, 10, 100]]))

```

Since the first **n** is unmodified, this is the same as:

```
lambda n: sum(i * j for i, j in zip([n / i for i in [4, 32, 256]], [1, 10, 100]])) + n

```

Since 4, 32, and 256 are all powers of two, they can be translated into bit shifts.

```
lambda n: sum(i * j for i, j in zip([n >> i for i in [2, 5, 8]], [1, 10, 100]])) + n

```

The golfiness doesn't translate well in Python, but turning the lists into Jelly strings of code page indices reduces Jelly's byte count.

```
lambda n: sum(i * j for i, j in zip([n >> i for i in map(jelly_codepage.index, '£¦®')], map(jelly_codepage.index, '¢½d'))) + n

```

## Jelly, 24 bytes

```
“¡¿ɼcÞµ³Ṡf2ż’bȷ3ŒPS€Ṣ
ị¢

```

Try it online!

# Answer
> 2 votes
# Ruby, ~~28~~ 27 bytes

```
->x{("%o"%x).tr"4-7","5-8"}

```

Try it online!

### Explanation

Output octal string, replace digits 4..7 with 5..8

# Answer
> 1 votes
# Bash + GNU utilities, 20

```
dc -e8o?p|tr 4-7 5-8

```

Reads a zero-indexed index from STDIN.

Try it online.

# Answer
> 1 votes
# 05AB1E, 20 bytes

```
9LD3%n>s3/óTsm*æO{sè

```

Try it online!

---

1-indexed, using the formula of `[(n%3)^2 + 1]*10^floor(n/3)` to generate the first 10 terms, then using powerset to calculate all possible combinations... Then I sort it and pull `a[b]`.

---

See it in action below:

```
Full program: 9LD3%n>s3/óTsm*æO{sè
current >> 9  ||  stack: []
current >> L  ||  stack: ['9']
current >> D  ||  stack: [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
current >> 3  ||  stack: [[1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 2, 3, 4, 5, 6, 7, 8, 9]]
current >> %  ||  stack: [[1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 2, 3, 4, 5, 6, 7, 8, 9], '3']
current >> n  ||  stack: [[1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 2, 0, 1, 2, 0, 1, 2, 0]]
current >> >  ||  stack: [[1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 4, 0, 1, 4, 0, 1, 4, 0]]
current >> s  ||  stack: [[1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 1, 2, 5, 1, 2, 5, 1]]
current >> 3  ||  stack: [[2, 5, 1, 2, 5, 1, 2, 5, 1], [1, 2, 3, 4, 5, 6, 7, 8, 9]]
current >> /  ||  stack: [[2, 5, 1, 2, 5, 1, 2, 5, 1], [1, 2, 3, 4, 5, 6, 7, 8, 9], '3']
current >> ó  ||  stack: [[2, 5, 1, 2, 5, 1, 2, 5, 1], [0.3333333333333333, 0.6666666666666666, 1.0, 1.3333333333333333, 1.6666666666666667, 2.0, 2.3333333333333335, 2.6666666666666665, 3.0]]
current >> T  ||  stack: [[2, 5, 1, 2, 5, 1, 2, 5, 1], [0, 0, 0, 1, 1, 1, 2, 2, 2]]
current >> s  ||  stack: [[2, 5, 1, 2, 5, 1, 2, 5, 1], [0, 0, 0, 1, 1, 1, 2, 2, 2], 10]
current >> m  ||  stack: [[2, 5, 1, 2, 5, 1, 2, 5, 1], 10, [0, 0, 0, 1, 1, 1, 2, 2, 2]]
current >> *  ||  stack: [[2, 5, 1, 2, 5, 1, 2, 5, 1], [1, 1, 1, 10, 10, 10, 100, 100, 100]]
current >> æ  ||  stack: [[2, 5, 1, 20, 50, 10, 200, 500, 100]]
current >> O  ||  stack: < OMITTED, THE RESULT OF POWERSET IS HUGE >
current >> {  ||  stack: [[0, 2, 5, 1, 20, 50, 10, 200, 500, 100, 7, 3, 22, 52, 12, 202, 502, 102, 6, 25, 55, 15, 205, 505, 105, 21, 51, 11, 201, 501, 101, 70, 30, 220, 520, 120, 60, 250, 550, 150, 210, 510, 110, 700, 300, 600, 8, 27, 57, 17, 207, 507, 107, 23, 53, 13, 203, 503, 103, 72, 32, 222, 522, 122, 62, 252, 552, 152, 212, 512, 112, 702, 302, 602, 26, 56, 16, 206, 506, 106, 75, 35, 225, 525, 125, 65, 255, 555, 155, 215, 515, 115, 705, 305, 605, 71, 31, 221, 521, 121, 61, 251, 551, 151, 211, 511, 111, 701, 301, 601, 80, 270, 570, 170, 230, 530, 130, 720, 320, 620, 260, 560, 160, 750, 350, 650, 710, 310, 610, 800, 28, 58, 18, 208, 508, 108, 77, 37, 227, 527, 127, 67, 257, 557, 157, 217, 517, 117, 707, 307, 607, 73, 33, 223, 523, 123, 63, 253, 553, 153, 213, 513, 113, 703, 303, 603, 82, 272, 572, 172, 232, 532, 132, 722, 322, 622, 262, 562, 162, 752, 352, 652, 712, 312, 612, 802, 76, 36, 226, 526, 126, 66, 256, 556, 156, 216, 516, 116, 706, 306, 606, 85, 275, 575, 175, 235, 535, 135, 725, 325, 625, 265, 565, 165, 755, 355, 655, 715, 315, 615, 805, 81, 271, 571, 171, 231, 531, 131, 721, 321, 621, 261, 561, 161, 751, 351, 651, 711, 311, 611, 801, 280, 580, 180, 770, 370, 670, 730, 330, 630, 820, 760, 360, 660, 850, 810, 78, 38, 228, 528, 128, 68, 258, 558, 158, 218, 518, 118, 708, 308, 608, 87, 277, 577, 177, 237, 537, 137, 727, 327, 627, 267, 567, 167, 757, 357, 657, 717, 317, 617, 807, 83, 273, 573, 173, 233, 533, 133, 723, 323, 623, 263, 563, 163, 753, 353, 653, 713, 313, 613, 803, 282, 582, 182, 772, 372, 672, 732, 332, 632, 822, 762, 362, 662, 852, 812, 86, 276, 576, 176, 236, 536, 136, 726, 326, 626, 266, 566, 166, 756, 356, 656, 716, 316, 616, 806, 285, 585, 185, 775, 375, 675, 735, 335, 635, 825, 765, 365, 665, 855, 815, 281, 581, 181, 771, 371, 671, 731, 331, 631, 821, 761, 361, 661, 851, 811, 780, 380, 680, 870, 830, 860, 88, 278, 578, 178, 238, 538, 138, 728, 328, 628, 268, 568, 168, 758, 358, 658, 718, 318, 618, 808, 287, 587, 187, 777, 377, 677, 737, 337, 637, 827, 767, 367, 667, 857, 817, 283, 583, 183, 773, 373, 673, 733, 333, 633, 823, 763, 363, 663, 853, 813, 782, 382, 682, 872, 832, 862, 286, 586, 186, 776, 376, 676, 736, 336, 636, 826, 766, 366, 666, 856, 816, 785, 385, 685, 875, 835, 865, 781, 381, 681, 871, 831, 861, 880, 288, 588, 188, 778, 378, 678, 738, 338, 638, 828, 768, 368, 668, 858, 818, 787, 387, 687, 877, 837, 867, 783, 383, 683, 873, 833, 863, 882, 786, 386, 686, 876, 836, 866, 885, 881, 788, 388, 688, 878, 838, 868, 887, 883, 886, 888]]
current >> s  ||  stack: [[0, 1, 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22, 23, 25, 26, 27, 28, 30, 31, 32, 33, 35, 36, 37, 38, 50, 51, 52, 53, 55, 56, 57, 58, 60, 61, 62, 63, 65, 66, 67, 68, 70, 71, 72, 73, 75, 76, 77, 78, 80, 81, 82, 83, 85, 86, 87, 88, 100, 101, 102, 103, 105, 106, 107, 108, 110, 111, 112, 113, 115, 116, 117, 118, 120, 121, 122, 123, 125, 126, 127, 128, 130, 131, 132, 133, 135, 136, 137, 138, 150, 151, 152, 153, 155, 156, 157, 158, 160, 161, 162, 163, 165, 166, 167, 168, 170, 171, 172, 173, 175, 176, 177, 178, 180, 181, 182, 183, 185, 186, 187, 188, 200, 201, 202, 203, 205, 206, 207, 208, 210, 211, 212, 213, 215, 216, 217, 218, 220, 221, 222, 223, 225, 226, 227, 228, 230, 231, 232, 233, 235, 236, 237, 238, 250, 251, 252, 253, 255, 256, 257, 258, 260, 261, 262, 263, 265, 266, 267, 268, 270, 271, 272, 273, 275, 276, 277, 278, 280, 281, 282, 283, 285, 286, 287, 288, 300, 301, 302, 303, 305, 306, 307, 308, 310, 311, 312, 313, 315, 316, 317, 318, 320, 321, 322, 323, 325, 326, 327, 328, 330, 331, 332, 333, 335, 336, 337, 338, 350, 351, 352, 353, 355, 356, 357, 358, 360, 361, 362, 363, 365, 366, 367, 368, 370, 371, 372, 373, 375, 376, 377, 378, 380, 381, 382, 383, 385, 386, 387, 388, 500, 501, 502, 503, 505, 506, 507, 508, 510, 511, 512, 513, 515, 516, 517, 518, 520, 521, 522, 523, 525, 526, 527, 528, 530, 531, 532, 533, 535, 536, 537, 538, 550, 551, 552, 553, 555, 556, 557, 558, 560, 561, 562, 563, 565, 566, 567, 568, 570, 571, 572, 573, 575, 576, 577, 578, 580, 581, 582, 583, 585, 586, 587, 588, 600, 601, 602, 603, 605, 606, 607, 608, 610, 611, 612, 613, 615, 616, 617, 618, 620, 621, 622, 623, 625, 626, 627, 628, 630, 631, 632, 633, 635, 636, 637, 638, 650, 651, 652, 653, 655, 656, 657, 658, 660, 661, 662, 663, 665, 666, 667, 668, 670, 671, 672, 673, 675, 676, 677, 678, 680, 681, 682, 683, 685, 686, 687, 688, 700, 701, 702, 703, 705, 706, 707, 708, 710, 711, 712, 713, 715, 716, 717, 718, 720, 721, 722, 723, 725, 726, 727, 728, 730, 731, 732, 733, 735, 736, 737, 738, 750, 751, 752, 753, 755, 756, 757, 758, 760, 761, 762, 763, 765, 766, 767, 768, 770, 771, 772, 773, 775, 776, 777, 778, 780, 781, 782, 783, 785, 786, 787, 788, 800, 801, 802, 803, 805, 806, 807, 808, 810, 811, 812, 813, 815, 816, 817, 818, 820, 821, 822, 823, 825, 826, 827, 828, 830, 831, 832, 833, 835, 836, 837, 838, 850, 851, 852, 853, 855, 856, 857, 858, 860, 861, 862, 863, 865, 866, 867, 868, 870, 871, 872, 873, 875, 876, 877, 878, 880, 881, 882, 883, 885, 886, 887, 888]]
current >> è  ||  stack: [[0, 1, 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22, 23, 25, 26, 27, 28, 30, 31, 32, 33, 35, 36, 37, 38, 50, 51, 52, 53, 55, 56, 57, 58, 60, 61, 62, 63, 65, 66, 67, 68, 70, 71, 72, 73, 75, 76, 77, 78, 80, 81, 82, 83, 85, 86, 87, 88, 100, 101, 102, 103, 105, 106, 107, 108, 110, 111, 112, 113, 115, 116, 117, 118, 120, 121, 122, 123, 125, 126, 127, 128, 130, 131, 132, 133, 135, 136, 137, 138, 150, 151, 152, 153, 155, 156, 157, 158, 160, 161, 162, 163, 165, 166, 167, 168, 170, 171, 172, 173, 175, 176, 177, 178, 180, 181, 182, 183, 185, 186, 187, 188, 200, 201, 202, 203, 205, 206, 207, 208, 210, 211, 212, 213, 215, 216, 217, 218, 220, 221, 222, 223, 225, 226, 227, 228, 230, 231, 232, 233, 235, 236, 237, 238, 250, 251, 252, 253, 255, 256, 257, 258, 260, 261, 262, 263, 265, 266, 267, 268, 270, 271, 272, 273, 275, 276, 277, 278, 280, 281, 282, 283, 285, 286, 287, 288, 300, 301, 302, 303, 305, 306, 307, 308, 310, 311, 312, 313, 315, 316, 317, 318, 320, 321, 322, 323, 325, 326, 327, 328, 330, 331, 332, 333, 335, 336, 337, 338, 350, 351, 352, 353, 355, 356, 357, 358, 360, 361, 362, 363, 365, 366, 367, 368, 370, 371, 372, 373, 375, 376, 377, 378, 380, 381, 382, 383, 385, 386, 387, 388, 500, 501, 502, 503, 505, 506, 507, 508, 510, 511, 512, 513, 515, 516, 517, 518, 520, 521, 522, 523, 525, 526, 527, 528, 530, 531, 532, 533, 535, 536, 537, 538, 550, 551, 552, 553, 555, 556, 557, 558, 560, 561, 562, 563, 565, 566, 567, 568, 570, 571, 572, 573, 575, 576, 577, 578, 580, 581, 582, 583, 585, 586, 587, 588, 600, 601, 602, 603, 605, 606, 607, 608, 610, 611, 612, 613, 615, 616, 617, 618, 620, 621, 622, 623, 625, 626, 627, 628, 630, 631, 632, 633, 635, 636, 637, 638, 650, 651, 652, 653, 655, 656, 657, 658, 660, 661, 662, 663, 665, 666, 667, 668, 670, 671, 672, 673, 675, 676, 677, 678, 680, 681, 682, 683, 685, 686, 687, 688, 700, 701, 702, 703, 705, 706, 707, 708, 710, 711, 712, 713, 715, 716, 717, 718, 720, 721, 722, 723, 725, 726, 727, 728, 730, 731, 732, 733, 735, 736, 737, 738, 750, 751, 752, 753, 755, 756, 757, 758, 760, 761, 762, 763, 765, 766, 767, 768, 770, 771, 772, 773, 775, 776, 777, 778, 780, 781, 782, 783, 785, 786, 787, 788, 800, 801, 802, 803, 805, 806, 807, 808, 810, 811, 812, 813, 815, 816, 817, 818, 820, 821, 822, 823, 825, 826, 827, 828, 830, 831, 832, 833, 835, 836, 837, 838, 850, 851, 852, 853, 855, 856, 857, 858, 860, 861, 862, 863, 865, 866, 867, 868, 870, 871, 872, 873, 875, 876, 877, 878, 880, 881, 882, 883, 885, 886, 887, 888], '32']
50
stack > [50]

```

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

```
n=>--n+(n>>2)+(n>>5)*10+(n>>8)*100

```

Or 32 bytes using the correct 0-indexing:

```
f=
n=>n+(n>>2)+(n>>5)*10+(n>>8)*100
```

```
<input type=number min=0 max=511 value=0 oninput=o.textContent=f(+this.value)><pre id=o>0
```

# Answer
> 0 votes
# Pyth, 12 bytes

Uses Dennis' witchcraft.

```
jkiR5.DR4jQ8

```

**Try it here.**

# Pyth,  ~~16 15~~  13 bytes

```
e.f!@,9 4jZTt

```

**Verify all the test cases.**

Thanks to Erik the Outgofer for some ideas.

# Answer
> 0 votes
# Jelly, 20 bytes

```
53b6×þ“¢½d‘FŒPS€Ṣị@‘

```

Try it online!

I know this is longer than the existing answer but I think this approach is golfable from here :P

-2 bytes thanks to Erik the Outgolfer

# Answer
> 0 votes
# Retina, 42 bytes

```
.+
$*1;
+`(1+)\1{7}
$1;
1111
1$&
(1*);
$.1

```

Try it online! Link includes test cases. 0-indexed. Explanation:

```
.+
$*1;

```

Convert from decimal to unary, with a `;` suffix.

```
+`(1+)\1{7}
$1;

```

Convert to octal, but still using unary representation of the digits with `;` after each unary value.

```
1111
1$&

```

Add 1 to the values 4-7.

```
(1*);
$.1

```

Convert each value plus its suffix to decimal.

# Answer
> 0 votes
# , 67 bytes

```
main(n){scanf("%d",&n);printf("%d",n+(n>>2)+(n>>5)*10+(n>>8)*100);}

```

A direct port from Neil's JavaScript answer, but I thought this should be added for completeness.

---

Tested on GCC version 6.3.0. It will throw some warnings, but compile anyway.

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


title: Compute the Wilson numbers

text:
# Question
Title: Compute the Wilson numbers
Given a positive integer *n*, compute the *nth* Wilson number *W(n)* where

and *e* = 1 if *n* has a primitive root modulo *n*, otherwise *e* = -1. In other words, *n* has a primitive root if there does not exist an integer *x* where 1 \< *x* \< *n-1* and *x*2 = 1 mod *n*.

* This is so create the shortest code for a function or program that computes the *nth* Wilson number for an input integer *n* \> 0.
* You may use either 1-based or 0-based indexing. You may also choose to output the first *n* Wilson numbers.
* This is the OEIS sequence A157249.

## Test Cases

```
n  W(n)
1  2
2  1
3  1
4  1
5  5
6  1
7  103
8  13
9  249
10 19
11 329891
12 32
13 36846277
14 1379
15 59793
16 126689
17 1230752346353
18 4727
19 336967037143579
20 436486
21 2252263619
22 56815333
23 48869596859895986087
24 1549256
25 1654529071288638505

```

# Answer
> 8 votes
# Jelly, ~~8~~ 7 bytes

1 byte thanks to Dennis.

```
gRỊTP‘:

```

Try it online!

You don't really have to compute `e` since you need to divide anyway.

# Answer
> 6 votes
# Husk, 11 bytes

```
S÷ȯ→Π§foε⌋ḣ

```

Try it online!

### Explanation

```
          ḣ   Range from 1 to input
     §foε⌋    Keep only those whose gcd with the input is 1
    Π         Product
  ȯ→          Plus 1
S÷            Integer division with input

```

# Answer
> 3 votes
# Mathematica, 91 bytes

```
If[(k=#)==1,2,(Times@@Select[Range@k,CoprimeQ[k,#]&]+If[IntegerQ@PrimitiveRoot@#,1,-1])/#]&

```

# Answer
> 3 votes
# Pyth, 11 bytes

```
/h*Ff>2iTQS

```

Try it here!

---

# How?

* `/h*Ff>2iTQS` \- Full program.
* `S` \- Generate the inclusive range **\[1, input\]**
* `f` \- Filter-keep those:

+ `iTQ` \- whose GCD with the input.
    + `>2` \- Is less than two (can be replaced by either of the following: `q1`, `!t`)
* `*F` \- Apply multiplication repeatedly. In other words, the product of the list.
* `h` \- Increment the product by 1.
* `/` \- Floor division with the input.

**TL;DR**: Get all the coprimes to the input in the range **\[1, input\]**, get their product, increment it and divide it by the input.

# Answer
> 2 votes
# Python 2, 62 bytes

```
n=input();k=r=1
exec'r*=k/n*k%n!=1or k/n;k+=1;'*n*n
print-~r/n

```

Try it online!

# Answer
> 2 votes
# J, 33 bytes

```
3 :'<.%&y>:*/(#~1&=@(+.&y))1+i.y'

```

This one is more of a request to see an improvement than anything else. I tried a tacit solution first, but it was longer than this.

# explanation

This is fairly straightforward translation of Mr. Xcoder's solution into J.

Try it online!

# Answer
> 2 votes
# , 82 bytes

```
function(n)(prod((1:n)[g(n,1:n)<2])+1)%/%n
g=function(a,b)ifelse(o<-a%%b,g(b,o),b)

```

Uses integer division rather than figuring out `e` like many answers here, although I did work out that `e=2*any((1:n)^2%%n==1%%n)-1` including the edge case of `n=1` which I thought was pretty neat.

Uses rturnbull's vectorized GCD function.

Try it online!

# Answer
> 2 votes
# 05AB1E, 8 bytes

```
Lʒ¿}P>I÷

```

Try it online!

# Answer
> 2 votes
## JavaScript (ES6), ~~72~~ ~~70~~ 68 bytes

```
f=(n,p=1,i=n,a=n,b=i)=>i?f(n,b|a-1?p:p*i,i-=!b,b||n,b?a%b:i):-~p/n|0
```

```
<input type=number min=1 oninput=o.textContent=f(+this.value)><pre id=o>
```

Integer division strikes again. Edit: Saved 2 bytes thanks to @Shaggy. Saved a further 2 bytes by making it much more recursive, so it may fail for smaller values than it used to.

# Answer
> 2 votes
# Pari/GP, 36 bytes

```
n->(prod(i=1,n,i^(gcd(i,n)==1))+1)\n

```

Try it online!

# Answer
> 2 votes
# Haskell, 42 bytes

```
f n=div(product[x|x<-[1..n],gcd x n<2]+1)n

```

Try it online!

Uses the integer division trick as all the other answers.
Uses 1-based indices.

**Explanation**

```
f n=                                       -- function
    div                                  n -- integer division of next arg by n
       (product                            -- multiply all entries in the following list
               [x|                         -- return all x with ...
                  x<-[1..n],               -- ... 1 <= x <= n and ...
                            gcd x n<2]     -- ... gcd(x,n)==1
                                      +1)  -- fix e=1

```

# Answer
> 1 votes
# Japt, 11 bytes

```
õ fjU ×Ä zU

```

Try it

---

## Explanation

Implicit input of integer `U`.

```
õ

```

Generate an array of integers from 1 to `U`.

```
fjU

```

Filter (`f`) co-primes of `U`.

```
×

```

Reduce by multiplication.

```
Ä

```

Add 1.

```
zU

```

Divide by `U`, floor the result and implicitly output.

# Answer
> 1 votes
# Axiom, 121 bytes

```
f(n)==(e:=p:=1;for i in 1..n repeat(if gcd(i,n)=1 then p:=p*i;e=1 and i>1 and i<n-1 and(i*i)rem n=1=>(e:=-1));(p+e)quo n)

```

add some type, ungolf that and result

```
w(n:PI):PI==
   e:INT:=p:=1
   for i in 1..n repeat
       if gcd(i,n)=1 then p:=p*i
       e=1 and i>1 and i<n-1 and (i*i)rem n=1=>(e:=-1)
   (p+e)quo n

(5) -> [[i,f(i)] for i in 1..25]
   (5)
   [[1,2], [2,1], [3,1], [4,1], [5,5], [6,1], [7,103], [8,13], [9,249],
    [10,19], [11,329891], [12,32], [13,36846277], [14,1379], [15,59793],
    [16,126689], [17,1230752346353], [18,4727], [19,336967037143579],
    [20,436486], [21,2252263619], [22,56815333], [23,48869596859895986087],
    [24,1549256], [25,1654529071288638505]]
                                                  Type: List List Integer

(8) -> f 101
   (8)
  9240219350885559671455370183788782226803561214295210046395342959922534652795_
   041149400144948134308741213237417903685520618929228803649900990099009900990_
   09901
                                                    Type: PositiveInteger

```

# Answer
> 1 votes
# JavaScript (ES6), ~~83~~ ~~81~~ ~~80~~ ~~78~~ ~~76~~ 68 bytes

My first pass at this was a few bytes longer than Neil's solution, which is why I originally ditched it in favour of the array reduction solution below. I've since golfed it down to tie with Neil.

```
n=>(g=s=>--x?g(s*(h=(y,z)=>z?h(z,y%z):--y?1:x)(n,x)):++s)(1,x=n)/n|0

```

---

### Try it

```
o.innerText=(f=
n=>(g=s=>--x?g(s*(h=(y,z)=>z?h(z,y%z):--y?1:x)(n,x)):++s)(1,x=n)/n|0
)(i.value=8);oninput=_=>o.innerText=f(+i.value)
```

```
<input id=i type=number><pre id=o>
```

---

# Non-recursive, 76 bytes

I wanted to give a non-recursive solution a try to see how it would turn out - not as bad as I expected.

```
n=>-~[...Array(x=n)].reduce(s=>s*(g=(y,z)=>z?g(z,y%z):y<2?x:1)(--x,n),1)/n|0

```

---

## Try it

```
o.innerText=(f=
n=>-~[...Array(x=n)].reduce(s=>s*(g=(y,z)=>z?g(z,y%z):y<2?x:1)(--x,n),1)/n|0
)(i.value=8);oninput=_=>o.innerText=f(+i.value)
```

```
<input id=i type=number><pre id=o>
```

---
Tags: code-golf, math, sequence, number-theory, primes
---


# Question
Title: Traverse a directory tree and output a list of all files
Write the shortest code that traverses a directory tree and outputs a flat list of all files.

* It should traverse the whole directory tree
* The order in which it enters sub-directories doesn't matter
* The directories should not be output
* The output should be a plain list — the definition is flexible, but it shouldn't contain irrelevant data
* You are free to use any programming technique

# Answer
# find 14 characters (12 on GNU)

```
find . -type f

```

Run this in the directory you want to list. Add `-printf '%f\n'` to only print names without the path.

Non-portable: `find -type f`.
> 8 votes

# Answer
# Pure Bash, 7

"ls -R" and "find" are the obvious, already mentioned common shell utilities. For completeness, we also have this pure bash option (no utility programs):

```
echo **

```

This requires the "globstar" shell option to be set with `shopt -s globstar`.

# Note:

This works only for Bash 4.0 and greater.
> 6 votes

# Answer
# Python

Aleksi Torhamo's answer is the correct and idiomatic one. My answer is just an exercise of what if there was no `os.walk`.

I was inspired by an elegant recursive function for Emacs Lisp that does the same.

```
from os import *
from os.path import *
def walk(path):
    return [basename(f) for f in listdir2(path) if not isdir(f)] +\
        sum([walk(f) for f in listdir2(path) if isdir(f)], [])

```

`listdir2` here is a non-existent function that returns absolute paths of files in a directory. Unfortunately, `listdir` doesn't return absolute paths, therefore i had to manually enter and exit directories with `chdir`, so my result wasn't a slick one-liner.

```
from os import *
from os.path import *
def walk(path, old_path):
    chdir(path)
    result = [f for f in listdir(path) if not isdir(f)] +\
        sum([walk(join(path, f), getcwd()) for f in listdir(path) if isdir(f)], [])
    chdir(old_path)
    return result

```

To understand it you must read about `os.chdir`, `os.getcwd`, `os.listdir`, `os.path.isdir`, `os.path.basename`, `os.path.join`, `sum`. The function creates a list of files and recursively repeats this for sub-directories. The list of sub-directories is summed up and appended to the list of original files.

We iterate thru list 2 times, this is inefficient. Better to partition the list into files and directories in one go. This answer proposes a smart use of `reduce`:

```
reduce(lambda x, y: x[not p(y)].append(y) or x, l, ([], []))

```

# Attempt #1 (~~179~~ 171)

```
from os import*
def w(p,o):chdir(p);r=[f for f in listdir(p)if not path.isdir(f)]+sum([w(path.join(p,f),getcwd())for f in listdir(p)if path.isdir(f)],[]);chdir(o);return r

```

# Attempt #2 (~~190~~ 178)

```
from os import *
def u(p,o):chdir(p);a,b=reduce(lambda x,y:x[path.isdir(y)].append(y)or x,listdir(p),([],[]));r=a+sum((u(path.join(p,c),getcwd())for c in b),[]);chdir(o);return r

```
> 4 votes

# Answer
# DOS (11 characters)

`dir/s/b/a-d`

I love the simplicity, `/s` allows `dir` to traverse through all subfolders, while `/b` suppresses the header and directory information. `/a-d` suppresses outputting of directories. A quick check to see if the additional space was required, and I was happy enough to submit this...
> 4 votes

# Answer
# Python3 - 53 characters

Two equally long ways for doing it:

```
import os;print(*sum((x[2]for x in os.walk('.')),[]))

```

and

```
import os;print(*sum(list(zip(*os.walk('.')))[2],[]))

```

These print the filenames separated by spaces on one line, I assumed that counts as a "flat list".
> 3 votes

# Answer
# C - 203 194

This example works when compiled with TCC:

```
t(char*p){DIR*d;struct dirent*e;if(d=opendir(p))while(e=readdir(d)){char*n=e->d_name,f[PATH_MAX];sprintf(f,"%s/%s",p,n);if((*n++-46|*n&(*n++-46|*n))&&!t(f))printf("%s\n",f);}return!closedir(d);}

```

This recursive function displays the path of every file present in the folder which path has been given as a parameter.

*Note:* one character had to be added to get the same result with GCC:

```
int t(char*p){DIR*d;struct dirent*e;if(d=opendir(p))while(e=readdir(d)){char f[PATH_MAX];char*n=e->d_name;sprintf(f,"%s/%s",p,n);if((*n++-46|*n&&(*n++-46|*n))&&!t(f))printf("%s\n",f);}return!closedir(d);}

```

I replaced `&` with `&&` in the condition. I guess the `&` operator has priority over `&&` in TCC syntax, while the opposite occurs with GCC.

See the full working example here: http://ideone.com/lGBtJw

# C - 220 215 (full program with include)

I liked that Coaumdio used a full program to answer... so I started adapting mine, here is the result:

```
#include<dirent.h>
main(i,char**p){DIR*d=opendir(*++p);char*n,f[4096],*a=f;struct dirent*e;d||puts(*p);if(d)while(e=readdir(d))sprintf(f,"%s/%s",*p,n=e->d_name),(*n++-46|*n&&(*n++-46|*n))&&main(i,&a-1);closedir(d);}

```

Expanded version:

```
#include<dirent.h>

int main(int i,char**p){
    DIR*d=opendir(*++p);
    char f[4096],*n,*a=f;
    struct dirent*e;
    d||puts(*p);
    if(d)while(e=readdir(d))
        sprintf(f,"%s/%s",*p,n=e->d_name),
        (*n++-46|*n&&(*n++-46|*n))&&main(i,&a-1);
    closedir(d);
}

```

Usage:

```
gcc list_files.c -o list_files
./list_files /var

```
> 3 votes

# Answer
**Bash**, 18

```
ls -R

```

**Windows CMD.**

```
dir /S

```

Compliant version

```
ls -R1|grep -v ^./

```
> 2 votes

# Answer
# C, 216 228 chars (#include included)

The other C solution contians nice tricks, but as I like compilable complete C solutions, here is my shot:

```
#include <dirent.h>
main(int _,char**v){char n[4096],*a=n,*b;DIR*d;struct dirent*e;(d=opendir(*++v))||puts(*v);while(d&&(e=readdir(d)))b=e->d_name,sprintf(n,"%s/%s",*v,b),strcmp(".",b)&&strcmp("..",b)&&main(0,&a-1);}

```

It's also a recursive traversal algorithm, and it's using the `main` function as recursive function. The main function tries to open the path contained in `argv[1]`. If it fails, it prints it, otherwise, it calls main on every sub-element (if it's different from `"."` or `".."`).

## Usage

It's a standalone, working C program:

```
$ gcc dir.c -o dir
$ ./dir /var.log
/var/log/kern.log.1
/var/log/alternatives.log.1
/var/log/user.log.2.gz
/var/log/nvidia-installer.log
/var/log/debug.4.gz
/var/log/wtmp.1
/var/log/lastlog
/var/log/messages.2.gz
/var/log/vmware-installer
/var/log/pm-powersave.log
/var/log/syslog.4.gz
/var/log/news/news.err
/var/log/news/news.notice
/var/log/news/news.crit
/var/log/apt/history.log.3.gz
/var/log/apt/history.log.9.gz
/var/log/apt/history.log.4.gz
/var/log/apt/term.log.10.gz
/var/log/apt/history.log.10.gz
/var/log/apt/term.log.4.gz

```

## Tips

I used a few (somewhat classic) C tricks:

* replace `if(condition)statement` with `contition && statement`
* replace `if(!condition)statement` with `condition || statement`
* use the `,` operator to save `{` and `}` in the while code

Here is a readable version:

```
#include <dirent.h>
main(int _,char**v) {
    char n[4096], *a=n,*b;
    DIR *d;
    struct dirent *e;
    (d = opendir(*++v)) || puts(*v);
    while(d && (e = readdir(d)))
        b = e->d_name,
        sprintf(n, "%s/%s", *v, b),
        strcmp(".", b)&&strcmp("..", b)&&
            main(0, &a-1);
}

```

## Edit

I have to insert a `closedir(d);` statement at the end, because a limit is reached when too much folders are opened (wild guess: the *open files* limit) and the the program stops. This happens only for folder containing many other folders.

the code is now:

```
#include <dirent.h>
main(int _,char**v){char n[4096],*a=n,*b;DIR*d;struct dirent*e;(d=opendir(*++v))||puts(*v);while(d&&(e=readdir(d)))b=e->d_name,sprintf(n,"%s/%s",*v,b),strcmp(".",b)&&strcmp("..",b)&&main(0,&a-1);closedir(d);}

```
> 2 votes

# Answer
## Groovy 58

```
new File("/").eachFileRecurse(){if(it.isFile())println it}

```
> 1 votes

# Answer
### CMD - 32 Bytes

Another CMD / DOS method -

```
for /r %a in (*)do @echo %~dpnxa

```

The `/r` switch recursively looks through a directory (defaulting to current directory), while `%~dpnxa` outputs `%a`, the current directory or file in the loop, to the following output format -

`d` \- drive
`p` \- path
`n` \- name
`x` \- extension

Because `x` is specified it will only output files, ignoring directories.
> 1 votes

# Answer
# Groovy 45

Now even shorter:

```
new File(".").traverse{if(it.file)println it}

```

Uses one of the traverse() methods available since Groovy 1.7.1.

# Groovy 46 ;-)

Another nice solution, if you don't count the required `import` statement, is this one:

```
import groovy.io.FileType.*
new File(".").traverse type:FILES,{println it}

```
> 1 votes

# Answer
# Ruby 18 characters

```
puts Dir['./**/*']

```
> 1 votes

# Answer
# Java 11, 52 bytes

```
Files.list(Path.of("")).forEach(System.out::println)

```

# Java, 87 bytes

```
void t(File f){if(f.isFile())System.out.println(f);else for(File c:f.listFiles())t(c);}

```
> 0 votes

# Answer
# SmileBASIC, 78 bytes

```
DIM F$[0],D$[0]FILES"//",D$@L
FILES POP(D$),F$WHILE LEN(F$)?POP(F$)WEND
GOTO@L

```

Displays a `*` or  before each filename, depending on whether it's a text file (is this allowed?)
> 0 votes

---
Tags: code-golf, tree-traversal, file-system
---


# Question
Title: Writing rational numbers as ratio of factorials of primes
Note: this challenge has been posted on the sandbox.

# Introduction

This challenge is inspired by 2009 Putnam B1, a problem in an undergraduate mathematics competition. The problem is as follows:

> Show that every positive rational number can be written as a quotient of products of factorials of (not necessarily distinct) primes. For example,

# Challenge

Your challenge is to take a pair of relatively prime positive integers, representing the numerator and denominator of a positive rational number (or just the rational number itself) as input, and output two lists (or arrays, etc.) of prime numbers so that the inputted rational number is equal to the ratio of the product of the factorials of the primes in the first list to the product of the factorials of the primes in the second list.

### Notes

* There may not be any primes that contained both in the first list and in the second list; however, a prime may appear as many times as one wishes in either list.
* The inputs can be assumed to each be (nonstrictly) between 1 and 65535; however, it cannot be assumed that the factorials of the numbers you will need to output will be in this range.

# Example Input and Output

Here are examples of legal inputs and outputs.

```
input=>output
10,9 => [2,5],[3,3,3]
2,1 => [2],[]
3,1 => [3],[2]
1,5 => [2,3,2],[5]     (elements of a list may be in any order)
3,2 => [3],[2,2]
6,1 => [3],[]

```

The inputs (2,2), (0,3), (3,0), (3,6) and (1,65536) are illegal inputs (i.e. your program doesn't need to behave in any particular way on them). Here are some examples of illegal outputs:

```
1,2 => [2],[2,2] (2 is in both returned lists)
5,2 => [5],[2,4] (4 is not prime)
2,1 => [2],[1] (1 is not prime either)
3,2 => [3],[2] (3!/2! = 3, not 3/2)

```

# Scoring

This is , so the lowest score in bytes wins!

# Answer
> 5 votes
# 05AB1E, ~~54~~ ~~53~~ ~~48~~ ~~46~~ ~~40~~ ~~35~~ ~~33~~ ~~32~~ 28 bytes

```
[D¿÷Z#DÓ€gZD<ØŠQ*DˆR!*]¯øεʒĀ

```

Try it online! Edit: Saved 2 bytes thanks to @ASCII-only. Saved ~~1~~ ~~2~~ ~~3~~ 4 bytes thanks to @Emigna. (I only need to save one more and I'm down to half my original byte count!) Explanation:

```
[       Begin an infinite loop
D¿÷     Reduce to lowest terms
Z#      Exit the loop if the (largest) value is 1
DÓ€g    Find the index of the largest prime factor of each value
Z       Take the maximum
D<ØŠ    Convert index back to prime and save for later
Q       Convert to an pair of which value had the largest prime factor
*       Convert to an pair with that prime factor and zero
Dˆ      Save the pair in the global array for later
R!*     Multiply the other input value by the factorial of the prime
]       End of infinite loop
¯ø      Collect all the saved primes
εʒĀ     Forget all the saved 0s

```

# Answer
> 5 votes
# Mathematica, ~~175~~ ~~177~~ ~~169~~ ~~154~~ 108 bytes

```
Join@@@Table[x[[1]],{s,{1,-1}},{x,r@#},x[[2]]s]&@*(If[#==1,1,{p,e}=Last@(r=FactorInteger)@#;p^e#0[p!^-e#]]&)

```

Try it online!

### How it works

This is the composition of two functions. The first, which ungolfs to

```
If[# == 1,
  1,
  {p,e} = Last[FactorInteger[#]];
  p^e * #0[p!^-e * #]
]&

```

is a recursive function for actually computing the desired factorization. Specifically, given a rational input `x`, we compute the primes whose factorials should be in the numerator and denominator, and return the fraction with all of those primes multiplied together. (For example, on input `10/9 = 2!*5!/(3!*3!*3!)`, we return `10/27 = 2*5/(3*3*3)`.)

We do this by dealing with the largest prime factor at every step: if pe occurs in the factorization of x, we make sure p!e occurs in the factorial-factorization, and recurse on x divided by p!e.

(Earlier, I had a more clever strategy that avoids large numbers by looking at the previous prime number before p, but Mathematica can handle numbers as big as 65521! easily, so there's no point. The old version you can find in the history is much faster: on my computer, it took 0.05 seconds on inputs that this version handles in 1.6 seconds.)

The second function turns the output of the first function into lists of primes.

```
Join @@@
  Table[x[[1]],
    {s,{1,-1}},
    {x,FactorInteger[#]},
    x[[2]]*s
  ]&

```

For `s=1` (positive powers) and `s=-1` (negative powers), and for each term `{prime,exponent}` in the factorization `r@#`, we repeat the prime number `prime` `exponent*s` many times.

# Noncompeting version with ~~109~~ 62 bytes

```
If[#==1,∇1=1,{p,e}=Last@FactorInteger@#;(∇p)^e#0[p!^-e#]]&

```

Same as above, but instead of giving output as a list, gives output as an expression, using the ∇ operator (because it has no built-in meaning) as a stand-in for factorials. Thus, an input of `10/9` gives an output of `(∇2*∇5)/(∇3)^3` to represent `(2!*5!)/(3!)^3`.

This is shorter because we skip the second part of the function.

---

*+2 bytes: the assignment `f=First` has to be done in the right place to keep Mathematica from getting upset.*

*-8 bytes: fixed a bug for integer outputs, which actually made the code shorter.*

*-15 bytes: `FactorInteger` returns sorted output, which we can take advantage of.*

*-46 bytes: we don't actually need to be clever.*

# Answer
> 2 votes
## Python 2, ~~220~~ ~~202~~ ~~195~~ 183 bytes

```
g=lambda a,b:a and g(b%a,a)or b;n,d=input();m=c=()
while n+d>2:
 t=n*d;f=p=2
 while t>p:
	if t%p:p+=1;f*=p
	else:t/=p
 if n%p:c+=p,;n*=f
 else:m+=p,;d*=f
 t=g(n,d);n/=t;d/=t
print m,c

```

Try it online! Edit: Saved ~~18~~ 25 bytes thanks to @Mr.Xcoder. Saved 12 bytes thanks to @JonathanFrech.

---
Tags: code-golf, math, number-theory, primes, rational-numbers
---


# Question
Title: Kolakoski-like self-referencing sequences
This is how the Kolakoski sequence (OEIS A000002) is defined:

> The Kolakoski sequence is a sequence that contains `1` and `2`, and the `n`th element of the sequence is the length of the `n`th group of equal elements (run) in the sequence itself. The first 20 terms of the sequence and the respective lengths are:
>
> ```
> 1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 1
> - --- --- - - --- - --- --- - --- --- -
> 1  2   2  1 1  2  1  2   2  1  2   2  1
>
> ```
>
> Essentially, the lengths of the groups of equal elements of the Kolakoski sequence is the Kolakoski sequence itself.

So far, so good, but that why should we restrict ourselves to `1` and `2`? We're not going to! Given two inputs, an array of positive integers `A` and an integer `N`, return the first `N` terms of the Kolakoski-like sequence defined by cycling through `A`. To get the grasp of it better, here is a worked example with the lengths of the newly added groups in brackets:

```
A = [2, 3, 1]
N = 25

2: [[2], 2 ]
3: [ 2 ,[2], 3 , 3 ]
1: [ 2 , 2 ,[3], 3 , 1 , 1 , 1 ]
2: [ 2 , 2 , 3 ,[3], 1 , 1 , 1 , 2 , 2 , 2 ]
3: [ 2 , 2 , 3 , 3 ,[1], 1 , 1 , 2 , 2 , 2 , 3 ]
1: [ 2 , 2 , 3 , 3 , 1 ,[1], 1 , 2 , 2 , 2 , 3 , 1 ]
2: [ 2 , 2 , 3 , 3 , 1 , 1 ,[1], 2 , 2 , 2 , 3 , 1 , 2 ]
3: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 ,[2], 2 , 2 , 3 , 1 , 2 , 3 , 3 ]
1: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 ,[2], 2 , 3 , 1 , 2 , 3 , 3 , 1 , 1 ]
2: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 ,[2], 3 , 1 , 2 , 3 , 3 , 1 , 1 , 2 , 2 ]
3: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 , 2 ,[3], 1 , 2 , 3 , 3 , 1 , 1 , 2 , 2 , 3 , 3 , 3 ]
1: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 , 2 , 3 ,[1], 2 , 3 , 3 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 1 ]
2: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 1 ,[2], 3 , 3 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 1 , 2 , 2 ]
C: [ 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 1 , 2 , 3 , 3 , 1 , 1 , 2 , 2 , 3 , 3 , 3 , 1 , 2 , 2 ]

```

Here is another worked example with a leading `1`:

```
A = [1, 2, 3]
N = 10

1: [[1]]
2: [ 1 ,[2], 2 ]
3: [ 1 , 2 ,[2], 3 , 3 ]
1: [ 1 , 2 , 2 ,[3], 3 , 1 , 1 , 1 ]
2: [ 1 , 2 , 2 , 3 ,[3], 1 , 1 , 1 , 2 , 2 , 2 ]
C: [ 1 , 2 , 2 , 3 , 3 , 1 , 1 , 1 , 2 , 2 ]

```

As you can see above, the final result was cut to `N = 10` elements. The `n`th element should be how long the `n`th equal-element group is, even if the element itself belongs in the group it refers to. As in the above case, the first `1` refers to the first such group which is just that `1`, and the first `2` refers to the second such group, which starts with it.

## Rules

* You may assume that `A` will never have two or more consecutive equal elements. `A` may contain an integer more than once, but the first and last elements will not be equal, and `A` will contain at least 2 elements (e.g. `[1, 2, 2, 3]`, `[2, 4, 3, 1, 2]` and `[3]` aren't going to be given). That's because if there were consecutive equal elements, the final result would've been an invalid prefix for such a sequence.
* You may assume `A` only contains positive integers (as such a sequence would be otherwise undefined).
* You may assume `N` is a non-negative integer (`N >= 0`).
* You can't return more terms than requested.
* Using any one of the standard loopholes is strictly forbidden.
* You may use any reasonable I/O method.
* Your answer doesn't have to work beyond natural language limits, but in theory your algorithm should work for arbitrarily large inputs and integers.
* This is , so the shortest answer wins.

## Test cases

```
[5, 1, 2], 0 -> []
[2, 3, 1], 25 -> [2, 2, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 2]
[1, 2, 3], 10 -> [1, 2, 2, 3, 3, 1, 1, 1, 2, 2]
[1, 2], 20 -> [1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1]
[1, 3], 20 -> [1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3, 1, 1, 1, 3]
[2, 3], 50 -> [2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3]
[7, 4], 99 -> [7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4, 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 7, 7, 7, 4]
[1, 2, 3], 5 -> [1, 2, 2, 3, 3]
[2, 1, 3, 1], 2 -> [2, 2]
[1, 3, 5], 2 -> [1, 3]
[2, 3, 2, 4], 10 -> [2, 2, 3, 3, 2, 2, 2, 4, 4, 4]

```

# Answer
> 9 votes
# Husk, 8 bytes

```
Ṡωȯ↑⁰`Ṙ¢

```

Takes first the length, then the list. Try it online!

## Explanation

```
Ṡωȯ↑⁰`Ṙ¢  Inputs: n=9 and x=[2,1,3]
Ṡωȯ       Apply the following function to x until a fixed point is reached:
           Argument is a list, say y=[2,2,1,3,3,3]
       ¢   Cycle x: [2,1,3,2,1,3..
     `Ṙ    Replicate to lengths in y: [2,2,1,1,3,2,2,2,1,1,1,3,3,3]
   ↑⁰      Take first n elements: [2,2,1,1,3,2,2,2,1]
          Final result is [2,2,1,1,3,2,1,1,1], print implicitly.

```

# Answer
> 8 votes
# Pyth, 14 bytes

```
u<s*V]M*QlGGvz

```

Try it online: Demonstration or Test suite

### Explanation:

```
u                 start with G = input array
       *QlG       repeat input array
     ]M           put every element into its own list
   *V      G      repeat every list vectorized by the counts in G
  s               flatten
 <          vz    take the first (second input line) numbers
                  and assign them to G until you reach fixed point

```

# Answer
> 5 votes
# , ~~120~~ ~~114~~ 108 bytes

*-6 bytes thanks to plannapus*

```
function(A,N){i=inverse.rle
w=length
a=rle(A)
while(w(a$l)<N){a[[1]]=i(a)
a[[2]]=rep(A,l=w(a$l))}
i(a)[0:N]}

```

Try it online!

Anonymous function; successively inverts the RLE, replacing the lengths `a[[1]]` with the inverted RLE, and the values `a[[2]]` with `A` replicated to a length equal to that of `a$l`.

# Answer
> 5 votes
# Java 8, ~~151 + 19~~ ~~119~~ 115 bytes

```
a->n->{int c=0,l[]=new int[n],i=0,j;for(;i<n;i++)for(j=0;j<(c==i?a[i]:l[i])&c<n;j++)l[c++]=a[i%a.length];return l;}

```

Try it online!

# Answer
> 5 votes
# Haskell, 68 bytes

Many thanks to Laikoni and flawr for their help in debugging and golfing this answer in the PPCG Haskell chatroom, Of Monads and Men. Golfing suggestions welcome! Try it online!

```
(.f).take
f a@(z:_)=(z<$[1..z])++do i<-[1..];cycle a!!i<$[1..f a!!i]

```

The first line is an anonymous function. The second line is the infinite list comprehension that produces our Kolakoski-like sequence.

**Explanation**

First, we define `z` as the head of `a` with `a@(z:_)`. Then, we initialize the sequence with `(z<$[1..z])`.

Then, from `1` onwards, `do i<-[1..]`, we append the following to the sequence: `cycle a!!i<$[1..f a!!i]`, which is the `i`-th member of `a` (cycled indefinitely) appended `f a!!i` times.

Finally, the anonymous function simply takes the first `n` terms of our Kolaskoski-like sequence.

# Answer
> 1 votes
# Python 2, 123 bytes

```
x,y=input()
k=x[0]
t,j=[],0
if k==1:t,j=[k]+x[1]*[x[1]],2
while len(t)<y:t+=(j and t[j]or k)*[x[j%len(x)]];j+=1
print t[:y]

```

Try it online!

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


title: Roots and operators

text:
# Question
Title: Roots and operators
I used to play a game while I was in the car, it consisted in taking the `n-1` first numbers of another car plate and use operators and roots on them to get the `n`th number of the plate.

I could use the following operators and roots :

* addition (ex: 1 + 1 = 2)
* subtraction (ex: 2 - 4 = -2)
* division (ex: 10 / 2 = 5) (Note that the division is only allowed if it returns an integer)
* multiplication (ex: 7 * 7 = 49)
* square root (ex : sqrt(36) = 6) (Note : must return an integer to be used)
* cubic root (ex : cbrt(8) = 2) (Note : must return an integer to be used)
* multiplication by -1 (ex : 8 * -1 = -8)
* power 2 (ex : 2² = 4)
* power 3 (ex : 2^3 = 8)
* leave the integer as it was (ex : 3 = 3)

The operations must be done in order! Which means you have to do the operations between the first and the second integer before an operation between the second and the third.

Example : you can do `(3 + 9) * 4` but not `3 + 9*4` if you have `[3,9,4,x,y,z,...]` as input

Moreover, you can use a unary operator on an integer before doing an operation.

Example : you can do `3² - 7^3`

But powers and roots are only allowed on one integer and not on the results of previous operations.

Example : you're not allowed to do `(3+7)²`

Note that multiplication and division are done that way : it's the applications of the previous operations that's multiplied or divided. For instance :

`[x,y,z,t,h] => (x+y)/z + t`

`[x,y,z,t,h] => (x-y+z) * t`

**YOUR TASK**

Your code will take as input an array of integers of size `n`, the `n-1` first integers will be the one used to obtain the `n`th number of the array.

You may use all the operators,roots and powers allowed by the rules above. Remember the integers must stay in the same orders to do the operations!

Your code will output a falsey value or an error if the `n`th number of the array cannot be obtained with the `n-1`first numbers of the array. On the other hand, if you can obtain the `n`th number you have to display the operations that led to it. Your code needs to output only one way of obtaining the `n`th number.

**TEST CASES**

(Note that I write square root sqrt and cube root cbrt but you can write it the way you want : x\**(1/3) for instance)

`[1] => error or 1`

`[2,8] => 2^3`

`[3,7,46] => 3*(-1) + 7²`

`[1,2,3,4] => 1*(-1) + 2 + 3`

`[0,0,0,0,0,0,0,8] => error`

`[7,4,3,8,16] => 7 + 4² - 3² + cbrt(8)`

`[28,4,8,7,5,1] => (28 - 4² - cbrt(8) - 7 ) / 5`

This is , thus the shortest answer in bytes wins!

# Answer
> 4 votes
# Python 2, ~~797~~ ~~547~~ ~~527~~ ~~515~~ ~~504~~ 503 bytes

```
s=eval("[('N,'%sN*-1,'(-%s)N*n,'%s^2N**3,'%s^3N**.5,'s(%s)N**(1./3),'c(%s)N+m,'%s+%sN-m,'%s-%sN*1./(m or.1),'(%s)/%sN*m,'(%s)*%s'),]".replace("N","'),(lambda n,m=0:n"))
P=__import__("itertools").product
def f(l):
 r=l.pop();L=len(l)
 for S in P(s[1:7],repeat=L):
	if any(s.index(x)>y<2for x,y in zip(S,l))<1<=L:
	 for D in P(s[7:],repeat=L-1):
		I,J=zip(*map(lambda((a,b),l):(a(l),b%l),zip(S,l)));R=I[0];C=J[0];e=0
		for a,b in D:I,J=I[1:],J[1:];R,C=a(R,I[0]),b%(C,J[0]);e=R%1or e
		if e<(R==r):return C

```

Try it online!

Returns `None` or a string with the calculation.

Prints:

* `(-n)` for `n*-1`
* `s(n)` for square root
* `c(n)` for cube root

**Explanation**

Works by checking all combinations of unary and binary operators on the input.

Outer loop gets all combinations of unary operations, which are applied to each number in the input list.

The inner loop then applies the binary operations on the result of the previous operation, and the next number.

If the result matches, a string with the calculation is returned.

Short-circuits a little by removing all outer loops where a number is `0` and the unary operator is not `n => n`, or the number is `1` and the operator is not `n => n` or `n => -n`

---
Tags: code-golf, math, number, arithmetic, expression-building
---


title: I don't like change!

text:
# Question
Title: I don't like change!
### Input:

Two strings without newlines or whitespaces.

### Output:

Both input strings on separate lines, with spaces where necessary for one of the two strings. And a third line with the characters `A`, `R`, `M` and , representing *added*, *removed*, *modified*, and *unchanged*.

We add spaces to either the top ***or*** bottom input string (if we have to). The goal of this challenge is to output with the least amount of changes (`ARM`) possible, also known as the Levenshtein distance.

### Example:

Let's say the input strings are `ABCDEF` and `AFBECD`, then the output would be this:

```
A B CDEF
AFBECD
 A A  RR

```

Here are some other possible invalid outputs as example (and there are a lot more):

```
ABCDEF
AFBECD
 MMMMM

A BCDEF
AFBECD
 A MMMR

AB CDEF
AFBECD
 MAMMMR

ABC DEF
AFBECD
 MMAMMR

ABC  DEF
AFBECD
 MMAA RR

ABCDEF
AFB ECD
 MMR MA

 AB CDEF   // This doesn't make much sense,
AFBECD     // but it's to show leading spaces are also allowed
AM A  RR

```

None of these have only four changes however, so only `A B CDEF\nAFBECD \n A A RR` is a valid output for this challenge.

### Challenge rules:

* You can assume the input strings won't contain any new-lines or spaces.
* The two input strings can be of different lengths.
* One of the two input strings should remain as is, except for optional leading/trailing spaces.
* If your languages doesn't support anything besides ASCII, you can assume the input will only contain printable ASCII characters.
* The input and output format are flexible. You can have three separate Strings, a String array, a single String with new-lines, 2D character array, etc.
* You are allowed to use something else instead of `ARM`, but state what you've used (i.e. `123`, or `abc.`, etc.)
* If more than one valid output is possible with the same amount of changes (`ARM`), you can choose whether to output one of the possible outputs or all of them.
* Leading and trailing spaces are optional:

```
A B CDEF
AFBECD
 A A  RR

```

or

```
"A B CDEF\nAFBECD\n A A  RR"
                 ^
                 Note there are no spaces here

```

### General rules:

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code.
* Also, please add an explanation if necessary.

### Test cases:

```
In: "ABCDEF" & "AFBECD"

Output (4 changes):
A B CDEF
AFBECD
 A A  RR

In: "This_is_an_example_text" & "This_is_a_test_as_example"

Possible output (13 changes):
This_is_an       _example_text
This_is_a_test_as_example
         MAAAAAAA        RRRRR

In: "AaAaABBbBBcCcCc" & "abcABCabcABC"

Possible output (10 changes):
AaAaABBbBBcCcCc
 abcABCab cABC
R MM  MMMR MM R

In: "intf(){longr=java.util.concurrent.ThreadLocalRandom.current().nextLong(10000000000L);returnr>0?r%2:2;}" & "intf(){intr=(int)(Math.random()*10);returnr>0?r%2:2;}"

Possible output (60 changes):
intf(){longr=java.util.concurrent.ThreadLocalRandom.current().nextLong(10000000000L);returnr>0?r%2:2;}
intf(){i ntr=(      i    n      t)(M  ath.r   andom        ()*         10          );returnr>0?r%2:2;}
       MR M  MRRRRRR RRRR RRRRRR MMMRR MMMMRRR     RRRRRRRR  MRRRRRRRRR  RRRRRRRRRR

In: "ABCDEF" & "XABCDF"

Output (2 changes):
 ABCDEF
XABCD F
A    R

In: "abC" & "ABC"

Output (2 changes):
abC
ABC
MM

```

# Answer
> 5 votes
# Haskell, ~~192~~ ~~181~~ ~~174~~ ~~161~~ ~~158~~ ~~150~~ ~~147~~ ~~143~~ 1581 bytes

```
e@(a:r)&f@(b:s)=snd$maximum[([1|' '<-s!!2],s)|s<-z(z(:))[a:" R",' ':b:"A",a:b:last("M":[" "|a==b])][r&f,e&s,r&s]]
x&y=[x,y,"RA"!!(0^length x)<$x++y]
z=zipWith

```

Try it online! Example usage: `"ABCDEF" & "AFBECD"`. Returns a list of three strings. This is an extension of my recursive solution to the ordinary Levenshtein distance question.

### Explanation:

To compute the minimal modifications to get from `"xyz"` to `"yw"`, we focus on the first character of both strings. There are three possibilities:

* *Remove:* Drop `x` from the first string and recursively compute the modifications to get from `"yz"` to `"yw"`. This yields the three lines `["yz","yw"," M"]`. Add `x` to the first one, a space to the second one and `R` to the third one. We get
```
xyz
yw
R M
```
* *Add:* Drop `y` from the second string and compute `"xyz" & "w"`, which returns the result `["xyz","w","MRR"]`. We need to add a space on the first line, `y` to the second and `A` to the third line:
```
 xyz
yw
AMRR
```
* *Modified/Unchanged:* We can combine those two cases because both require to drop the first character of both strings and compute the minimal modifications between the remaining strings: `"yz" & "w"`. To the result `["yz","w","MR"]`, we add `x` on he first and `y` on the second line. Only for the last line we need to differentiate whether the initial characters are the same. If they are the same, a space is added to the third line, otherwise (as in this case because `x \= y`) an `M` is added:
```
xyz
yw
MMR
```

From those three candidates, we need to find the one with the fewest modifications. This is equivalent to having the most spaces on the third line. Therefore we convert each candidate `s` (a list of three strings) to a tuple `([1|' '<-s!!2],s)`, where `s` appears as second component and the first component is a list with as many elements as there are spaces in the third line of `s` (`s!!2` because of 0-indexing). As list element `1` is used, but the actual element is irrelevant as long as it is the same for all candidates.

Altogether, this yields the list of tuples

```
[([1],["xyz"," yw","R M"]),([],[" xyz","yw","AMRR"]),([],["xyz","yw","MMR"])]
```
The build-in `maximum` selects the largest element of this list, where tuples are compared lexicographically, that is component-wise from left to right. As `[1]` is larger than `[]`, the first tuple is selected, and `snd` returns the second of component, that is the list of lines, of the tuple.

---

1 +15 bytes to fix a bug where `A`-changes at the end of a string would be displayed as `R`-changes

# Answer
> 8 votes
# JavaScript (ES6), ~~413~~ ... ~~343~~ 342 bytes

*Saved 5 bytes by tweaking the loop indices, as suggested by @KevinCruijssen*

Takes input as 2 strings in currying syntax. Returns an array of 3 strings.

```
b=>a=>{m=[];x=a.length;y=b.length;for(i=j=0,c=d='';i<=y;c+=R='R')m[i]=[[c,i++]];for(;j++<x;)m[i=0][j]=[d+=A='A',j];for(;i<y;i++)for(j=0;j<x;)[C]=m[[X,S]=m[i][j],[Y,I]=m[i+1][j],[Z,D]=m[i][++j],Q=[Z+R,D+1],i+1][j]=b[i]==a[j-1]?[X+' ',S]:S<I?D<S?Q:[X+'M',S+1]:D<I?Q:[Y+A,I+1];return[(g=s=>C.replace(/./g,c=>c==s?' ':b[i++],i=0))(A),g(R,b=a),C]}

```

### Test cases

```
let f =

b=>a=>{m=[];x=a.length;y=b.length;for(i=j=0,c=d='';i<=y;c+=R='R')m[i]=[[c,i++]];for(;j++<x;)m[i=0][j]=[d+=A='A',j];for(;i<y;i++)for(j=0;j<x;)[C]=m[[X,S]=m[i][j],[Y,I]=m[i+1][j],[Z,D]=m[i][++j],Q=[Z+R,D+1],i+1][j]=b[i]==a[j-1]?[X+' ',S]:S<I?D<S?Q:[X+'M',S+1]:D<I?Q:[Y+A,I+1];return[(g=s=>C.replace(/./g,c=>c==s?' ':b[i++],i=0))(A),g(R,b=a),C]}

console.log(f('ABCDEF')('AFBECD').join`\n`);
console.log(f('This_is_an       _example_text')('This_is_a_test_as_example').join`\n`);
console.log(f('AaAaABBbBBcCcCc')('abcABCabcABC').join`\n`);
console.log(f("intf(){longr=java.util.concurrent.ThreadLocalRandom.current().nextLong(10000000000L);returnr>0?r%2:2;}")("intf(){intr=(int)(Math.random()*10);returnr>0?r%2:2;}").join`\n`);
console.log(f('ABCDEF')('XABCDF').join`\n`);
```

### Less golfed

```
b => a => {
  m = []; x = a.length; y = b.length;

  // initialize the leftmost column and the topmost row
  for(i = j = 0, c = d = ''; i <= y; c += R = 'R')
    m[i] = [[c, i++]];
  for(; j++ < x;)
    m[i = 0][j] = [d += A = 'A', j];

  // walk through the Levenshtein matrix
  for(; i < y; i++)
    for(j = 0; j < x;)
      [C] = m[                                // C = current string, once updated
        [X, S] = m[i][j],                     // substitution
        [Y, I] = m[i + 1][j],                 // insertion
        [Z, D] = m[i][++j],                   // deletion
        Q = [Z + R, D + 1],                   // precomputed update for deletion
        i + 1
      ][j] =
        b[i] == a[j - 1] ?
          [X + ' ', S]                        // unchanged character
        :
          S < I ?
            D < S ? Q : [X + 'M', S + 1]      // deletion or substitution
          :
            D < I ? Q : [Y + A, I + 1];       // deletion or insertion

  return [
    // g = helper function to format the output strings by inserting spaces
    (g = s => C.replace(/./g, c => c == s ? ' ' : b[i++], i = 0))(A),
    g(R, b = a),

    // final modification string, picked from the last visited cell
    C
  ]
}

```

### Example

Below is the initial matrix for ***b = "foo"*** and ***a = "ok"***:

```
//                     'o'           'k'
[ [ [ '',    0 ], [ 'A',   1 ], [ 'AA',  2 ] ],
  [ [ 'R',   1 ],  (undefined),  (undefined) ],  // 'f'
  [ [ 'RR',  2 ],  (undefined),  (undefined) ],  // 'o'
  [ [ 'RRR', 3 ],  (undefined),  (undefined) ] ] // 'o'

```

and here is the final matrix after all iterations:

```
//                     'o'           'k'
[ [ [ '',    0 ], [ 'A',   1 ], [ 'AA',  2 ] ],
  [ [ 'R',   1 ], [ 'M',   1 ], [ 'MA',  2 ] ],  // 'f'
  [ [ 'RR',  2 ], [ 'R ',  1 ], [ 'R A', 2 ] ],  // 'o'
  [ [ 'RRR', 3 ], [ 'RR ', 2 ], [ 'R M', 2 ] ] ] // 'o'

```

The final modification string along with the Levenshtein distance are stored in the bottom-right cell.

# Answer
> 4 votes
# Python 2, ~~548~~ ~~536~~ ~~484~~ ~~5001~~ ~~488~~ ~~447~~ ~~3812~~ ~~373~~ ~~371~~ ~~357~~ 350 bytes

```
s,t=input()
n,m=len(s),len(t)
r=range
L=[[(j,'RA'[i<1]*j)for j in r(i,m-~i)]for i in r(n+1)]
for i in r(n):
 for j in r(m):M,R=L[i][j:j+2];A=L[i+1][j];v,V=min(A,R,M);x=('AR'[v in R],'M_'[s[i]==t[j]])[v in M];_=M;X=eval(x)[1]+x;L[i+1][j+1]=v+(x<'_'),X
for i in r(len(X)):s=s[:i]+' '*('B'>X[i])+s[i:];t=t[:i]+' '*('R'==X[i])+t[i:]
print s+'\n'+t+'\n'+X

```

Try it online!

Uses `'ARM_'` instead of `'ARM '`

Works by building up the Levenshtein matrix, ~~and then traversing backwards to find the operations~~. Now builds the operation-string at the same time as the Levenshtein matrix, as in Arnauld's JS answer

1: More bytes, as it did not work if the first string was a single character.

2: Switched to building the combinations in the Levenshtein matrix.

# Answer
> 1 votes
# Mathematica, 250 ~~256~~ ~~259~~ ~~384~~ bytes

~0.00035 seconds for the java code case.

```
(i=o=p="";a=Array;r=StringLength;If[Length@#>0,g=#&@@#;h=#[[2]];u=r@g;v=r@h;i=i<>g;o=o<>h;w=Abs[v-u];k=a[" "&,w];If[u<v,i=i<>k,o=o<>k];p=p<>a["M"&,u~Min~v];p=p<>a[If[u>v,"R","A"]&,w],i=i<>#;o=o<>#;p=p<>a[" "&,r@#]]&/@SequenceAlignment[#,#2];{i,o,p})&

```

Usage: `f["ABCDE", "ABCDF"]`

Try it online!

The code is based on a fact that `SequenceAlignment` works by default on

> With the default setting SimilarityRules-\>Automatic, each match between two elements contributes 1 to the total similarity score, while each mismatch, insertion, or deletion contributes -1.

Namely, the scoring is calculated by `M`, `A` and `R`, accordingly.

Example:

# Answer
> 1 votes
# Python 2, 310 bytes

```
from difflib import*
a,b=input()
U,j=[],' '
for g,s,t,x,y in SequenceMatcher(0,a,b).get_opcodes():
	g,Y,T=g[0],y-x,t-s
	z,A,B=Y-T,a[s:t],b[x:y]
	if'q'<g:U+=[A+z*j,B+j*-z,'M'*min(T,Y)+'A'*z+'R'*-z]
	if'e'==g:U+=[A,B,j*Y]
	if'i'==g:U+=[j*Y,B,'A'*Y]
	if'e'>g:U+=[A,j*T,'R'*T]
for e in[0,1,2]:print''.join(U[e::3])

```

Try it online!

Using `difflib.SequenceMatcher` that computes an alignment between two strings

# Answer
> 1 votes
# , ~~351~~ 345 bytes

-6 bytes thanx to KevinCruijssen

```
string f(string a,string b){import std.algorithm;string x,y,z;size_t i,j,k;foreach(c;levenshteinDistanceAndPath(a,b)[1]){final switch(c)with(EditOp){case none:x~=a[i++];y~=b[j++];z~=" ";break;case substitute:x~=a[i++];y~=b[j++];z~="M";break;case insert:x~=" ";y~=b[j++];z~="A";break;case remove:x~=a[i++];y~=" ";z~="R";}}return x~"\n"~y~"\n"~z;}

```

Try it online!

---
Tags: code-golf, string
---


title: How many unique primes?

text:
# Question
Title: How many unique primes?
One way to represent a natural number is by multiplying exponents of prime numbers. For example, 6 can be represented by 2^1\*3^1, and 50 can be represented by 2^1\*5^2 (where ^ indicates exponention). The number of primes in this representation can help determine whether it is shorter to use this method of representation, compared to other methods. But because I don't want to calculate these by hand, I need a program to do it for me. However, because I'll have to remember the program until I get home, it needs to be as short as possible.

## Your Task:

Write a program or function to determine how many distinct primes there are in this representation of a number.

## Input:

An integer n such that 1 \< n \< 10^12, taken by any normal method.

## Output:

The number of distinct primes that are required to represent the input, as outlined in the introduction.

## Test Cases:

```
24      -> 2 (2^3*3^1)
126     -> 3 (2^1*3^2*7^1)
1538493 -> 4 (3^1*11^1*23^1*2027^1)
123456  -> 3 (2^6*3^1*643^1)

```

This is OEIS A001221.

## Scoring:

This is , lowest score in bytes wins!

# Answer
# MATL, ~~4~~ 3 bytes

*-1 byte thanks to Luis Mendo*

```
YFz

```

Try it online!

```
YF         Exponents of prime factors
  z        Number of nonzeros

```

Original answer:

```
Yfun

```

Try it online!

A ver`Yfun` answer.

```
          (Implicit input)
Yf         Prime factorization
  u        Unique
   n       Numel
           (Implicit output)

```
> 6 votes

# Answer
# 05AB1E, 2 bytes

another pretty boring answer...

```
fg

```

A full program accepting a numeric input and printing the result

**Try it online!**

### How?

```
fg - implicitly take input
f  - get the prime factors with no duplicates
 g - get the length
   - implicit print

```
> 5 votes

# Answer
# Mathematica, 7 bytes

```
PrimeNu

```

Yup, there's a built-in.

# Mathematica, 21 bytes

```
Length@*FactorInteger

```

The long way around.
> 5 votes

# Answer
# Gaia, 2 bytes

Yet another pretty boring answer... --- J. Allan

```
ḋl

```

Try it online!

* \- Prime factorization as **\[prime, exponent\]** pairs.
* `l` \- Length.
> 5 votes

# Answer
# Bash + GNU utilities, 33

* 1 byte saved thanks to @Dennis

```
factor|grep -Po ' \d+'|uniq|wc -l

```

Try it online.

### Explanation

```
factor|                            # Split input into prime factors
       grep -Po ' \d+'|            # group factors onto lines
                       uniq|       # remove duplicates
                            wc -l  # count the lines

```
> 4 votes

# Answer
# Python 2, 56 bytes

```
f=lambda n,p=2,k=1:n/p and[f(n,p+1),k+f(n/p,p,0)][n%p<1]

```
> 4 votes

# Answer
# Retina, ~~31~~ 30 bytes

```
&`(?!(11+)\1+$)(11+)$(?<=^\2+)

```

Input is in unary.

*Thanks to @MartinEnder for golfing of 1 byte!*

Try it online! (includes decimal-to-unary converter)

### How it works

Since the program consists of a single regex with the `&` modifier, Retina simply counts the amount of *overlapping* matches. The input is assumed to consist of **n** repetitions of **1** and nothing else.

The negative lookahead

```
(?!(11+)\1+$)

```

matches at locations between **1**'s that are *not* followed by two or more **1**'s (`11+`), followed by one or more repetitions of the same amount of **1**'s (`\1+`), followed by the end of input (`$`).

Any composite number **ab** with **a, b \> 1** can be written as **b** repetitions of **a** repetitions of **1**, so the lookahead matches only locations followed by **p** repetitions of **1**, where **p = 1** or **p** is prime.

The regex

```
(11+)$

```

makes sure **p \> 1** by requiring at least two **1**'s (`11+`) and stores the tail of **1**'s in the second capture group (`\2`).

Finally, the positive lookbehind

```
(?<=^\2+)

```

verifies that the entire input consists of **kp** occurrences (**k ≥ 1**) of **1**, verifying that **p** divides the input.

Thus, each match corresponds to a unique prime divisor **p**.
> 4 votes

# Answer
# Jelly, 3 bytes

a pretty boring answer...

```
ÆFL

```

A monadic link taking a number and returning a number

**Try it online!**

### How?

```
ÆFL - Link: number, n
ÆF  - prime factorisation as a list of prime, exponent pairs
  L - length

```
> 3 votes

# Answer
# CJam, ~~7~~ 5 bytes

*Thanks to Martin Ender for 2 bytes off!*

```
{mF,}

```

Anonymous block (function) that expects the input number on the stack and replaces it by the output number.

Try it online! Or verify all test cases.

### Explanation

```
{   }   e# Define block
 mF     e# List of (prime, exponent) pairs
   ,    e# Length

```
> 3 votes

# Answer
# Ohm v2, 2 bytes

```
ml

```

Try it online!

The two built-ins are right next to each other in the documentation lol.
> 3 votes

# Answer
# Jelly, 2 bytes

Yet another pretty boring answer... --- J. Allan

```
Æv

```

Try it online!

A built-in.
> 3 votes

# Answer
## Alice, 10 bytes

```
/o
\i@/Dcd

```

Try it online!

### Explanation

```
/o
\i@/...

```

This is just the standard framework for linear arithmetic-heavy programs that need decimal I/O. The actual program itself is then just:

```
Dcd

```

Which does:

```
D    Deduplicate prime factors. Does what it sounds like: for every p^k which
     is a divisor n, this divides n by p^(k-1).
c    Push the individual prime factors of n. Since we've deduplicated them
     first, the number of factors is equal to the value we're looking for.
d    Push the stack depth, i.e. the number of unique prime factors.

```
> 3 votes

# Answer
# JavaScript 45 bytes

\*For @SEJPM request an explanation : what im doing here is this- im going from 2 - n (which changes, and eventually will be the biggest prime factor)- now if the current number divide n i want to count it only once(even though it can be a factor of 2\*2\*2\*3 - 2 is counted once)- so the "j" comes to the picture, when j is not specified in the call of the funcion - j will receive the value of "undefined" , and when n%i == 0 then i call the function with j=1 in the next call) - and then i only add 1 when j equals undefined which is !j + Function(n/i,i,(j=1 or just 1)). i dont change i in this matter becuase it may still be divisible by i again(2\*2\*3) but then j will equal 1 and it will not count as a factor. hope i explained it well enough.

```
P=(n,i=2,j)=>i>n?0:n%i?P(n,i+1):!j+P(n/i,i,1)

console.log(P(1538493)==4);
console.log(P(24)==2);
console.log(P(126)==3);
console.log(P(123456)==3);
```

if the last prime is very big than it will have max call stack- if its an issue i can make an iterative one
> 3 votes

# Answer
# Brachylog, 3 bytes

```
ḋdl

```

Try it online!

### Explanation

```
ḋ      Prime decomposition
 d     Remove duplicates
  l    Length

```
> 3 votes

# Answer
# Python 3, ~~68~~ 67 bytes

*1 byte removed thanks to @Mr.Xcoder*

```
lambda n:sum(n%k<all(k%j for j in range(2,k))for k in range(2,n+1))

```

This times out for the largest test cases. Try it online!
> 2 votes

# Answer
# Pyth, 3 bytes

```
l{P

```

Test suite

Length (`l`) of set (`{`) of prime factors (`P`) of the input.
> 2 votes

# Answer
# Husk, 3 bytes

```
Lup

```

Try it online!

### Explanation

```
  p  -- prime factors
 u   -- unique elements
L    -- length

```
> 2 votes

# Answer
# Actually, 2 bytes

Yet another pretty boring answer... --- J. Allan

```
yl

```

Try it online!

The first character can be replaced by `w`.
> 2 votes

# Answer
# Pyke, 3 bytes

```
P}l

```

Try it here!
> 2 votes

# Answer
# R + numbers, ~~30~~ 14 bytes

*16 bytes removed thanks to @Giuseppe*

```
numbers::omega

```

Also, here is the Try it online!! link per @Giuseppe.
> 2 votes

# Answer
# Convex, 3 bytes

```
mF,

```

Try it online!
> 1 votes

# Answer
# Japt, ~~5~~ 4 bytes

```
â èj

```

Try it

Get the divisors (`â`) and count (`è`) the primes (`j`).
> 1 votes

# Answer
# Haskell, 58 bytes

*-4 bytes thanks to @Laikoni*

```
f n=sum[1|x<-[2..n],gcd x n>1,all((>)2.gcd x)[2..x-1]]

```

Try it online!

**Explanation**

Essentially generates all primes at most as large as `n` and filters them for being a factor of n and then takes the length of the result.

```
f n=                                                   -- main function
    sum[                                             ] -- output the length of the list
        1|x<-[2..n],                                   -- consider all potential primes <=n
                                                       -- and insert 1 into the list if predicates are satisfied
                    gcd x n>1,                         -- which are a factor of n
                              all(          )[2..x-1]  -- and for which all smaller numbers satisfy
                                  (>)2.                -- 2 being larger than
                                       gcd x           -- the gcd of x with the current smaller number

```
> 1 votes

# Answer
# Pari/GP, 5 bytes

I don't know why it is called nu in Mathematica but omega in Pari/GP.

```
omega

```

Try it online!
> 1 votes

# Answer
# ARBLE, 28 bytes

```
len(unique(primefactors(n)))

```

Try it online!

*This is a very literal solution*
> 1 votes

# Answer
# Python 2,  ~~63~~  55 bytes

A much more interesting answer...

-8 bytes thanks to Jonathan Frech (use an argument with a default for the post-adjustment of the result of primes from `0` to `1` -- much better than a wrapping lambda!!)

```
f=lambda n,o=1:sum(n%i+f(i,0)<1for i in range(2,n))or o

```

A recursive function taking a positive integer, `n`, and returning a positive integer, the count.

**Try it online!** Really inefficient, don't even bother with the other test cases.
> 0 votes

# Answer
# Dyalog APL, 17 bytes

```
⎕CY'dfns'
≢∪3pco⎕

```

Try it online!
> 0 votes

# Answer
# J, 12 bytes

```
{:@$@(__&q:)

```

`q:` is J's prime exponents function, giving it the argument `__` produces a matrix whose first row is all nonzero prime factors and whose 2nd row is their exponents.

We take the shape `$` of that matrix -- rows by columns -- the number of columns is the answer we seek.

`{:` gives us the last item of this two items (num rows, num columns) list, and hence the answer.

Try it online!
> 0 votes

# Answer
# Java (OpenJDK 9), 67 bytes

```
n->{int c=0,p=1;for(;p<n;)if(n%++p<1)for(c++;n%p<1;n/=p);return c;}

```

Try it online!
> 0 votes

# Answer
# Javascript ES6, 56 chars

```
n=>eval(`for(q=2,r=0;q<=n;++q)n%q||(n/=q,r+=!!(n%q--))`)

```

Test:

```
f=n=>eval(`for(q=2,r=0;q<=n;++q)n%q||(n/=q,r+=!!(n%q--))`)
console.log([24,126,1538493,123456].map(f)=="2,3,4,3")
```
> 0 votes

# Answer
# Python 3 + primefac, 50 bytes

```
from primefac import*
lambda n:len({*primefac(n)})

```

---

# Python 2 + primefac, 52 bytes

```
from primefac import*
lambda n:len(set(primefac(n)))

```

**Try it online**
> 0 votes

# Answer
# Python 2, 50 bytes

```
f=lambda n,k=2,p=1:n/k and(n%k<p%k)+f(n,k+1,p*k*k)

```

Try it online!
> 0 votes

# Answer
```
import sys

X=int(sys.argv[1])
print X
b=2
a=0

while(b<X or b==X):
        if(X%b == 0):
                a=a+1;
                while(X%b==0):
                        X=X/b;
                b=b+1;
        else:
                b=b+1;

print a;

```
> -2 votes

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


title: Who's Going? Can you help me?

text:
# Question
Title: Who's Going? Can you help me?
If Abe goes, then Beth and Diana go. If Beth goes, then Catherine goes. If Catherine goes, then Diana goes. If Diana goes, then Ezra goes. Only three people go. Who goes?

# Challenge

Given a list of several pairings of people, such that in each pairing the second person goes if the first person goes, and a positive integer number of people who go, determine one or all possibilities of who goes. You may output either, as long as the output is consistent.

The example above may be represented in input by `[(A,B),(A,D),(B,C),(C,D),(D,E)],3`, which can be represented as a graph visually as:

```
A -> B -> C -> D -> E
⤷-------------⤴

```

If A goes, then everyone must go, so at least 5 people go, which cannot be 3 people.

If B goes, then C, D, and E must go, so at least 4 people go, which cannot be 3 people.

Thus we are left with C, D, and E going, yielding a final output of `[C,D,E]`.

The input `[(0,1),(0,3),(1,2),(2,3),(3,4)],3` represents the same situation and is the format given in the test cases (with output `[2,3,4]`).

We assume that no people other than the people in at least one pairing should be considered. For example, there is no person `5` or `F` in this example.

# I/O

Your program/function **must** input `g`, the list of pairings which represents a directed graph, and `n`, the number of people who will go. Input `g` may be taken in any format (such as an adjacency matrix) which does not encode additional information and can encode at least **25** people to consider (the example considered 5 people).

You may also (optionally) input `p`, the list of people, and/or `c`, the number of people to consider. List of people `p` given `g` (sorted). (append `L` to end to get number of people `c`).

Your program/function does not have to handle if:

* the integer input is greater than the number of people considered.
* the integer input is not positive
* repeat pairings
* reflexive pairings (e.g. `(A,A)` or `(0,0)`)
* impossible situations (e.g. `[(A,B),(B,A)],1`)

The output should be in any format which can represent a list from 1 to 24 people.

# Test Cases

If the output of a test case has an `OR` in it, your program may return any *one* or all of the choices.

```
[(0,1),(1,2),(2,3),(2,5),(5,6),(6,3),(6,7),(7,4)], 1 => [3] OR [4]
[(0,1),(1,2)], 1 => [2]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)], 1 => [7]
[(1,2),(2,3)], 2 => [2,3]
[(1,2),(3,4)], 2 => [1,2] OR [3,4] OR [2,4]
[(0,1),(1,2),(1,8),(2,3),(3,4),(4,11),(5,4),(5,6),(6,13),(13,20),(13,12),(12,19),(20,19),(4,19),(19,18),(11,10),(10,3),(10,2),(10,9),(9,8),(8,1),(8,7),(18,17),(18,24),(17,24),(24,23),(17,16),(16,23),(24,18),(16,15),(23,22),(22,15),(22,21),(21,14),(14,15)], 1 => [7] OR [15]
[(0,1),(1,0),(0,2),(1,3)], 1 => [2] OR [3]
[(0,1),(1,0),(0,2),(1,3)], 2 => [2,3]
[(0,1),(1,2)], 3 => [0,1,2]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 4 => [8,9,4,7]
[(0,1),(1,0),(0,2),(1,3)], 4 => [0,1,2,3]
[(0,1),(1,2),(2,3),(2,5),(5,6),(6,3),(6,7),(7,4)], 5 => [3,4,5,6,7]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 5 => [4,5,7,8,9]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)], 6 => [2,3,4,5,6,7]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)], 7 => [1,2,3,4,5,6,7]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 7 => [3,4,5,6,7,8,9]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 8 => [2,3,4,5,6,7,8,9]
[(0,1),(1,2),(2,3),(3,5),(3,6),(3,7),(5,7),(6,4),(7,9),(8,4),(9,8)], 9 => [1,2,3,4,5,6,7,8,9]
[(0,1),(1,2),(1,8),(2,3),(3,4),(4,11),(5,4),(5,6),(6,13),(13,20),(13,12),(12,19),(20,19),(4,19),(19,18),(11,10),(10,3),(10,2),(10,9),(9,8),(8,1),(8,7),(18,17),(18,24),(17,24),(24,23),(17,16),(16,23),(24,18),(16,15),(23,22),(22,15),(22,21),(21,14),(14,15)], 9 => [14,15,16,17,18,21,22,23,24]

```

# Answer
> 2 votes
# Husk, ~~14~~ 10 bytes

```
~f`öΠFf†€Ṗ

```

Takes three inputs: number of people to go, 2-row matrix of the constraints, and list of all people involved, in this order. Returns all possible lists of people who go. If you want to output only one list, replace the leftmost `f` by . Try it online!

## Explanation

The idea is to loop over the size-`n` subsets of `p` and keep those that satisfy the condition imposed by `g`: if the first person in a pair goes, then the second person must go too.

```
~f`öΠFf†€Ṗ  Implicit inputs, say n=3, g=[[1,3,3],[4,1,4]] and p=[1,2,3,4]
         Ṗ  All n-element subsets of p: [[1,2,3],[2,3,4],[1,3,4],[1,2,4]]
~f          Keep those subsets (say q=[1,2,4]) for which
  `ö        this function gives a truthy (nonzero) result:
       †     Deep map over g:
        €    index in q, or 0 if doesn't occur: [[1,0,0],[3,1,3]]
     Ff      Fold by select (filter second row by truthiness on first row): [3]
    Π        Product: 3

```

This program is one of those where it's really hard to explain how the program arguments are passed to the correct functions, but I'll try. First, `n` is the first argument, so it can be given to  directly, making it a function that takes a list and returns its `n`-subsets. The next two inputs are `g` and `p`, and the program's shape at this point is `~(f)(`öΠFf†€)(Ṗn)` with parentheses added for clarity. The operator `~` gives `g` to ``öΠFf†€` and `p` to `Ṗn`, and combines the results with `f`. `Ṗnp` is just the `n`-subsets of `p`, so that's simple. The operator ``` causes `öΠFf†€` to take its arguments in the reverse order, so `g` is actually the *second* argument of this function. The first argument is an element `q` of `Ṗnp`, which is extracted by `f` (filter). We give `q` as an argument to , which becomes a function for testing membership in `q`, and deep map *that* over the second argument, which is `g`. Then `ΠFf` are applied to the result. The role of `ö` is just to compose `ΠFf†€` into one function, which we can then pass on to ``` and `~f`.

# Answer
> 1 votes
# Python 2, 100 98 bytes

```
g,n=input()
v=k=0
while bin(v).count("1")^n:k=v=k+1;exec"for a,b in g:v|=(v>>a&1)<<b\n"*25
print v

```

I assume that the people are numbered from 0 to n. `g` is a list of pairs just like in the question. The output is a number where the `i`th bit is set if the `i`th person goes.

# Answer
> 1 votes
# Python 3, 97 95 bytes

```
lambda g,n,c:[k for k in range(2**c)if-1<bin(k).count("1")-n<all(k>>s&1for f,s in g if k>>f&1)]

```

Try it online!

Takes `g` as a list of pairs, as in the question, and additionally takes the number of people `c`. Returns all solutions in form `n` where bit `i` of `n` corresponds to whether or not person `i` attends.

# Answer
> 1 votes
# Wolfram Language (Mathematica), ~~62~~ 55 bytes

```
Select[g=#;#2~Subsets~{#3},#==g~VertexOutComponent~#&]&

```

Try it online!

### I/O

Takes as input the following three arguments:

* list of she-goes-I-go pairs, as rules (`x->y`). The first example in the question would be encoded as `{A->B,A->D,B->C,C->D,D->E}`. Can also take a Mathematica `Graph` object.
* list of people involved. E.g., `{A,B,C,D,E}`.
* number of people we want to go. E.g., `3`.

The output is a list of *all* subsets of people of the right size who could go.

### How it works

The older version was fancier, and contained the expression `#|##&@@#` which I'm very proud of, but this one just uses a built-in. `VertexOutComponent` computes the set of everyone else who must go, given a group of people who are going; we just `Select` the `Subsets` of the given size whose `VertexOutcomponent` is the same set and no bigger.

*-7 bytes: the built-in.*

---
Tags: code-golf, graph-theory
---


title: Multi-Base Primes

text:
# Question
Title: Multi-Base Primes
For the purpose of this challenge, a multi-base prime is a prime which, when written in base 10, is prime in one or more bases smaller than 10 and larger than 1 as well. All single-digit primes are trivially multi-base primes. 11 is also a multi-base prime, as 11 in binary is 3, which is prime (it is also prime in base 4 and base 6). The first few terms are: 2,3,5,7,11,13, 17, 23,31,37,41,43,47,53,61...

## Your Task:

Write a program or function that, when given an integer as input, returns/outputs a truthy value if the input is a multi-base prime, and a falsy value if it is not.

## Input:

An integer between 1 and 10^12.

## Output:

A truthy/falsy valule, depending on whether the input is a multi-base prime.

## Test Cases:

```
3    -> truthy
4    -> falsy
13   -> truthy
2003 -> truthy (Also prime in base 4)
1037 -> falsy (2017 in base 5 but not a prime in base 10)

```

## Scoring:

This is , lowest score in bytes wins!

# Answer
> 1 votes
# Python 2, ~~159~~ 137 bytes

```
f=lambda n:p(n)*any(p(b(n,i))for i in range(2,10))
p=lambda n:all(n%x for x in range(2,int(n**0.5)+1))
b=lambda n,i:n and n%i+10*b(n/i,i)

```

Try it online!

Saved 22 bytes thanks to ovs.

# Answer
> 0 votes
# Mathematica, 60 bytes

```
Or@@(p=PrimeQ)[FromDigits/@IntegerDigits[#,2~Range~9]]&&p@#&

```

Try it online!

# Answer
> 0 votes
# Japt, ~~15~~ 14 bytes

```
j ©Ao2@sX nÃdj

```

Try it

---

## Explanation

Implicit input of integer `U`.

```
j

```

Test if input is prime (Boo-urns to input validation!).

```
©

```

Logical AND (`&&`).

```
Ao2@    Ã

```

Generate an array of integers from `2` to `9` and pass each through a function where `X` is the current element.

```
sX n

```

Convert `U` to a base-`X` string (`s`) and back to an integer (`n`).

```
dj

```

Check if any of the numbers in the array are prime.

---
Tags: code-golf, decision-problem, primes, integer
---


title: Smaller-Base Palindromes

text:
# Question
Title: Smaller-Base Palindromes
For the purpose of this challenge, a smaller-base palindrome (SBP) is a number which is palindromic in a base between 1 and itself (exclusive), and is not a repdigit in the same base. For example, 5 is a SBP because it is a palindrome in base 2 (101). The first few SBPs are `5,9,10,16,17,20,21,23,25,26,27,28,29,33...`

## Your Task:

Write a program or function that, when given an integer `i` as input, returns/outputs the `i`th SBP.

## Input:

An integer `i` where `0 <= i < 1,000,000`.

## Output:

The `i`th SBP.

## Test Cases:

```
12 -> 29
18 -> 41

```

## Scoring:

This is , lowest score in bytes wins!

# Answer
> 7 votes
# Python 2, ~~133~~ 119 bytes

-3 thanks to Ovs

-5 thanks to Lynn

1-indexed

```
j=i=0
n=input()
while n:
 j+=1;l=[];N=i
 while N:l+=N%j,;N/=j
 if{i%j}<set(l)>l==l[::-1]or j>i:n-=j<i;i+=1;j=1
print~-i

```

Try it online!

# Answer
> 5 votes
# 05AB1E, 15 bytes

```
µNDLвʒÂQ}ʒË_}gĀ

```

Try it online!

**Explanation**

```
µ                 # loop until input matches are found
 N                # push current iteration number
  D               # duplicate
   L              # range
    в             # convert to each base
     ʒÂQ}         # filter, keep elements that are equal to their reverse
         ʒË_}     # filter, keep elements that are not all equal
             g    # length
              Ā   # is trueish (not zero)

```

# Answer
> 4 votes
# Jelly, 12 bytes

```
bṖEÐḟŒḂÐfµ#Ṫ

```

Try it online!

-2 thanks to Jonathan Allan, one being for, well, obvious stuff \>\_\>

Explanation:

```
bṖEÐḟŒḂÐfµ#Ṫ Special quick behavior requires full program
bṖEÐḟŒḂÐf #  Get the first (STDIN number)th integers with truthy results under this
             function starting from 0
 Ṗ             Make range [1..tested integer)
b              Convert the tested integer to each base in the range above
  EÐḟ          Remove repdigits (i.e. negative filter by all-equal)
     ŒḂÐf      Keep palindromes (i.e. filter by is palindrome)
         µ Ṫ Pop the last element of the integer list formed

```

# Answer
> 3 votes
# Pyth, 14 bytes

```
e.f_I#ft{TjLZS

```

Try it here.

1-indexed.

Explanation:

```
e.f_I#ft{TjLZSZQ Trailing ZQ is implicit
 .f            Q Find the first Q (input) positive integers that return a truthy result for
             SZ    Make range [1..Z (tested integer)]
          jLZ      Convert Z to each base in the range
      f            Filter by "non-repdigit"
        {T           Unique elements of T (tested element)
       t             Remove first element
   _I#             Filter by Invariant with Reverse (i.e. palindrome)
e                Take last element
```

# Answer
> 2 votes
# Python 2, 125 bytes

```
n=5
i=input()
while i:
 n+=1;b=1
 while b<n:
	b+=1;l=[];a=n
	while a:l+=a%b,;a/=b
	if{n%b}<set(l)>l==l[::-1]:i-=1;b=n
print n

```

Try it online!

`n` represents the integer we test for SBP-ness as we count up.

`i` is the input: it is decremented each time `n` is an SBP.

We loop over bases `b` from 2 to `n` inclusive\* and compute the (backwards) base-`b` representation of `n`: this is `l`. The only real magical part is the chained comparison `{n%b}<set(l)>l==l[::-1]`:

* `{n%b}<set(l)` makes sure `l` contains at least two distinct digits (i.e. `n` is not a repdigit), by checking that `{n%b}` is a *strict* subset of `set(l)`. (We know `n%b` is in `l` as `n%b` is the last digit of `n` in base `b`.)
* `set(l)>l` is always true because of how Python sorts types.
* `l==l[::-1]` checks that `l` is a palindrome.

One final trick is using `b=n` instead of `break` to exit the loop.

(\*It’s safe to include `n` in the loop, as `n` in base `n` is always `10`, which isn’t a palindrome. (`while b<n` looks like we exclude `n`, but note where the `b+=1` is!))

# Answer
> 1 votes
# Dyalog APL, 53 bytes

```
{{∨/∧/¨((1<≢∘∪)∧⌽=⊢)¨(⍵+1)⊥⍣¯1⍨¨1↓⍳⍵+1:⍵+1⋄∇⍵+1}⍣⍵⊢2}

```

Try it online!

# Answer
> 0 votes
# Perl 6, 83 bytes

```
{(5..*).grep({grep {.Set>1&&[.reverse]eqv$_},map {[.polymod($^a xx*)]},2..$_})[$_]}

```

Try it

## Expanded

```
{
  # create a list of SBPs
  (5 .. *).grep(
    {
      # find out if the current value is a SBP

      grep
      {    # parameter is $_
        .Set > 1              # is there more than one distinct digit?
        &&
        [.reverse] eqv $_     # is it the same in reverse?
      },
      map
      {    # parameter is $a
        [                     # put into an Array so it is not a one shot Seq
          .polymod( $^a xx *) # convert into new base
        ]
      },
      2 .. $_                 # possible bases
                              # (don't need to exclude $_ here)
    }

  )[ $_ ]                     # index into the list of SBPs
}

```

---
Tags: code-golf, sequence, base-conversion, palindrome
---


title: Narcissistic array elements

text:
# Question
Title: Narcissistic array elements
# Definition

Narcissistic 1 integers of an array think they are better than their neighbours, because they are strictly higher than their arithmetic mean.

Neighbours are defined as follows:

* If the integer is at index **0** (the first), then its neighbours are the last and the second elements of the list.
* If the integer is not the first nor the last, then its neighbours are the two immediately adjacent elements.
* If the integer is at index **-1** (the last), then its neighbours are the second-last and the first elements of the list.

---

# Task

Given an array of integers, your task is to discard the narcissistic ones.

* The integers can be positive, negative or zero.
* You may assume that the array contains at least three elements.
* All standard rules apply. This is , so the shortest code in bytes wins.

# Examples

Consider the array `[6, 9, 4, 10, 16, 18, 13]`. Then we can built the following table:

```
Element | Neighbours | Neighbours' Mean | Is Narcissistic?
--------+------------+------------------+-----------------
6       | 13, 9      | 11               | False.
9       | 6, 4       | 5                | True.
4       | 9, 10      | 9.5              | False.
10      | 4, 16      | 10               | False.
16      | 10, 18     | 14               | True.
18      | 16, 13     | 14.5             | True.
13      | 18, 6      | 12               | True.

```

By filtering the Narcissistic ones out, we are left with `[6, 4, 10]`. And that's it!

# Test Cases

```
Input -> Output

[5, -8, -9]                         -> [-8, -9]
[8, 8, 8, 8]                        -> [8, 8, 8, 8]
[11, 6, 9, 10]                      -> [6, 10]
[1, 2, 0, 1, 2]                     -> [1, 0, 1]
[6, 9, 4, 10, 16, 18, 13]           -> [6, 4, 10]
[6, -5, 3, -4, 38, 29, 82, -44, 12] -> [-5, -4, 29, -44]

```

 1 - *Narcissist* does not mean mathematically Narcissistic.

# Answer
> 7 votes
# Jelly, 10 bytes

```
ṙ2+ṙ-<ḤCx@

```

Try it online!

Explanation:

```
ṙ2+ṙ-<ḤCx@
ṙ2         Rotate the original list two elements to the left
  +        Add each element to the respective element of the original list
   ṙ-      Rotate the result one element to the right
     <Ḥ    Check if each element is less than the double of its respective element on the original list
       C   Subtract each 1/0 boolean from 1 (logical NOT in this case)
        x@ Repeat each element of the original list as many times as the respective element of the logical NOT (i.e. keep elements of the original list where the respective element from the result is 1)

```

# Answer
> 6 votes
## JavaScript (ES6), ~~57~~ 56 bytes

```
a=>a.filter((e,i)=>e+e<=a[(i||l)-1]+a[++i%l],l=a.length)

```

Edit: Saved 1 byte thanks to @g00glen00b.

# Answer
> 6 votes
# Python 2, 60 bytes

```
lambda x:[b for a,b,c in zip(x[-1:]+x,x,x[1:]+x)if b*2<=a+c]

```

Try it online!

# Answer
> 5 votes
# 05AB1E, ~~22~~ ~~17~~ ~~15~~ 14 bytes

```
vy¹®1‚N+èO;>‹—

```

Try it online!

```
vy             # For each...
  ¹            # Push array.
   ®1‚         # Push [1,-1]
      N+       # Add current index.
        è      # Push surrounding values of current index.
         O;    # Summed in half.
           >‹  # A <= B?
             — # If true, print current.

```

# Answer
> 5 votes
# Mathematica, 44 bytes

```
Pick[#,#<=0&/@(2#-(r=RotateLeft)@#-#~r~-1)]&

```

### How it works

Given input such as `{11,6,9,10}`, computes

```
2*{11,6,9,10} - {6,9,10,11} - {10,11,6,9}

```

and picks out the elements of the original input in places where this result is at most 0.

# Answer
> 4 votes
# Octave / MATLAB, 48 bytes

```
@(x)x(conv([x(end),x,x(1)],[1,-2,1],'valid')>=0)

```

**Try it online!**

### Explanation

The input array is first extended with the last (`x(end)`) and first (`x(1)`) entries at the appropriate sides.

The test for narcissism is done by `conv`olving the extended array with `[1, -2, 1]` and keeping only the `'valid'` part.

Comparing each entry in the convolution result with `0` gives a logical index (mask) which is used to select the numbers from the input.

# Answer
> 4 votes
# Haskell, 51 bytes

```
f s=[b|(a,b,c)<-zip3(last s:s)s$tail$s++s,b*2<=a+c]

```

Try it online! Usage example: `f [1,2,3]` yields `[1,2]`.

For `s = [1,2,3]`, `last s:s` is the list `[3,1,2,3]` and `tail$s++s` the list `[2,3,1,2,3]`. `zip3` generates a list of triples `(a,b,c)` from three given list, truncating the longer ones to the length of he shortest list. We get `[(3,1,2),(1,2,3),(2,3,1)]`, with `b` being the original list element and `a` and `c` its neighbours. The list comprehension then selects all `b` where `b*2<=a+c`, that is `b` is not narcissistic.

# Answer
> 2 votes
# Japt, ~~17~~ ~~16~~ 15 bytes

```
kÈ>½*[Y°ÉY]x!gU

```

Try it

---

## Explanation

Implicit input of array `U`.

```
kÈ>

```

Remove (`k`) the elements that return true when passed through a function, with `Y` being the current index, that check if the current element is greater then ...

```
[Y°ÉY]

```

The array `[Y-1, Y+1]` ...

```
x!gU

```

Reduced by addition (`x`) after indexing each element into `U` ...

```
½*

```

Multiplied by `.5`.

---

## Alternative, 15 bytes

```
fÈ+X§UgYÉ +UgYÄ

```

Try it

# Answer
> 2 votes
# , ~~51~~ 56 bytes

*Thanks to user2390246 for correcting my algorithm*

```
function(l)l[c(l[-1],l[1])+c(l[s<-sum(l|1)],l[-s])>=2*l]

```

Try it online!

indexes `l` where `c(l[-1],l[1])+c(l[s],l[-s])`, the neighbor-sums of `l`, are not less than twice `l`.

# Answer
> 2 votes
# Mathematica, 40 bytes

```
Pick[#,+##>=3#2&@@@Partition[#,3,1,-2]]&

```

# Answer
> 2 votes
# , 16 bytes

```
#~+:<:1&|.+_1&|.

```

Try it online!

## Explanation

```
#~+:<:1&|.+_1&|.  Input: array A
           _1&|.  Rotate A right by 1
      1&|.        Rotate A left by 1
          +       Add
  +:              Double each in A
    <:            Less than or equal to
#~                Copy the true values from A

```

# Answer
> 1 votes
# Python 2, ~~64~~ 60 bytes

* Saved four bytes thanks to xnor; golfing `l[-~j%len(l)]` (and a space) to `(l+l)[-~j]`.

```
lambda l:[k for j,k in enumerate(l)if(l+l)[-~j]+l[~-j]>=k+k]

```

Try it online!

# Answer
> 1 votes
# Jelly, 17 bytes

```
Ḣ+ṪH<ḢṆ
.ịj⁸Ç3ƤTị

```

Try it online!

# Answer
> 1 votes
# Java 8, ~~141~~ ~~137~~ 127 bytes

```
import java.util.*;a->{List r=new Stack();for(int i=0,l=a.length;i<l;)if(2*a[i]<=a[(i-1+l)%l]+a[++i%l])r.add(a[i-1]);return r;}

```

-10 bytes thanks to *@Nevay*.

**Explanation:**

Try it here.

```
import java.util.*;    // Required import for List and Stack

a->{                   // Method with integer-array parameter and List return-type
  List r=new Stack();  //  Return-list
  for(int i=0,         //  Index integer, starting at 0
      l=a.length;      //  Length of the input array
      i<l;)            //  Loop over the input array
    if(2*a[i]<=        //   If two times the current item is smaller or equal to:
        a[(i-1+l)%l]   //   The previous integer in the list
        +a[++i%l])     //   + the next integer in the list
      r.add(a[i-1]);   //    Add the current integer to the result-list
                       //  End of loop (implicit / single-line body)
  return r;            //  Return result-List
}                      // End of method

```

# Answer
> 1 votes
# Julia 0.6, 38 bytes

```
!x=x[x[[e=end;1:e-1]]+x[[2:e;1]].>=2x]

```

Try it online!

# Answer
> 0 votes
# JavaScript ES5 , 59 bytes

```
F=a=>a.filter((x,i)=>2*x<=a[-~i%(l=a.length)]+a[(i-1+l)%l])

console.log(""+F([5, -8, -9])==""+[-8, -9])
console.log(""+F([8, 8, 8, 8])==""+[8, 8, 8, 8])
console.log(""+F([11, 6, 9, 10])==""+[6, 10])
console.log(""+F([1, 2, 0, 1, 2])==""+[1, 0, 1])
console.log(""+F([6, 9, 4, 10, 16, 18, 13])==""+[6, 4, 10])
console.log(""+F([6, -5, 3, -4, 38, 29, 82, -44, 12])==""+[-5, -4, 29, -44])
```

# Answer
> 0 votes
# Perl 5, 51 + 1 (`-a`) = 52 bytes

```
$p=$F[-1];say map{$p+$F[++$i%@F]<2*($p=$_)?'':$_}@F

```

Try it online!

# Answer
> 0 votes
**PowerShell, 75 bytes**

```
for($i=0;$i-lt$a.Length;$i++){if($a[$i]-le(($a[$i-1]+$a[$i+1])/2)){$a[$i]}}

```

# Answer
> 0 votes
# APL, 20 bytes

```
{⍵/⍨⍵≤2÷⍨(1⌽⍵)+¯1⌽⍵}

```

Try it online!

---
Tags: code-golf, number, array
---