title: (RGS 1/5) Binary multiples

text:
# Question
Title: (RGS 1/5) Binary multiples
A *binary multiple* of a positive integer `k` is a positive integer `n` such that `n` is written only with `0`s and `1`s in base 10 and `n` is a multiple of `k`. For example, `111111` is a *binary multiple* of 3.

It is easy to show that a positive integer has infinitely many *binary multiples*. See here for a construction proof of one *binary multiple* for each `k`. Multiplying by powers of `10` you get infinitely many more.

# Your task

Given a positive integer `k`, return the smallest binary multiple of `k`.

# Input

A positive integer `k`.

# Output

A positive integer `n`, the smallest binary multiple of `k`.

# Test cases

```
2 -> 10
3 -> 111
4 -> 100
5 -> 10
6 -> 1110
7 -> 1001
8 -> 1000
9 -> 111111111
10 -> 10
11 -> 11
12 -> 11100
13 -> 1001
14 -> 10010
15 -> 1110
16 -> 10000
17 -> 11101
18 -> 1111111110
19 -> 11001
20 -> 100
100 -> 100

```

This is so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!

---

This is the first challenge of the RGS Golfing Showdown. If you want to participate in the competition, you have 96 hours to submit your eligible answers. Remember there is 450 reputation in prizes! (See **6** of the rules)

Otherwise, this is still a regular challenge, so enjoy!

# Answer
> 13 votes
# 05AB1E, 6 bytes

```
∞b.ΔIÖ

```

Try it online! or verify all test cases *(courtesy of @KevinCruijssen)*

---

## Explanation

```
∞b           - Infinite binary list
  .Δ         - Find the first value such that..
    IÖ       - It's divisible by the input

```

# Answer
> 11 votes
# Python 2, 42 bytes

```
f=lambda k,n=0:n*(max(`n`)<'2')or f(k,n+k)

```

Try it online!

---

Full program, same length:

```
a=b=input()
while'1'<max(`b`):b+=a
print b

```

Try it online!

# Answer
> 9 votes
# MATL, 10 bytes

```
`@YBUG\}HM

```

Try it online! Or verify all test cases.

### Explanation

```
`      % Do...while
  @    %   Push iteration index (1-based)
  YB   %   Convert to binary string (1 gvies '1', 2 gives '10,  etc).
  U    %   Convert string to number ('10' gives 10). This is the current
       %   solution candidate
  G    %   Push input
  \    %   Modulo. Gives 0 if the current candidate is a multiple of the
       %   input, which will cause the loop to exit
}      % Finally: execute on loop exit
  H    %   Push 2
  M    %   Push input to the second-last normal function (`U`); that is,
       %   the candidate that caused the loop to exit, in string form
       % End (implicit). If top of the stack is 0: the loop exits.
       % Otherwise: a new iteration is run
       % Display (implicit)

```

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

Looks for the smallest \\$n\\$ such that the decimal representation of \\$p=n\times k\\$ is made exclusively of \\$0\\$'s and \\$1\\$'s.

```
f=(k,p=k)=>/[2-9]/.test(p)?f(k,p+k):p

```

Try it online! (some test cases removed because of recursion overflow)

---

# JavaScript (ES6), 41 bytes

Looks for the smallest \\$n\\$ such that \\$k\\$ divides the binary representation of \\$n\\$ parsed in base \\$10\\$.

```
k=>(g=n=>(s=n.toString(2))%k?g(n+1):s)(1)

```

Try it online! (all test cases)

# Answer
> 8 votes
# , ~~50~~ 38 bytes

-4 bytes thanks to Giuseppe.

```
grep("^[01]+$",(k=scan())*1:10^k)[1]*k

```

Try it online!

It follows from this blog post (linked in the question) that the smallest binary multiple of \\$k\\$ is smaller than \\$2\cdot10^{k-1}\\$; this answer uses the larger bound \\$k\cdot10^k\\$ instead.

Creates a vector of all multiples of \\$k\\$ between \\$k\\$ and \\$k\cdot10^k\\$. The regexp gives the indices of those made only of 0s and 1s; select the first index and multiply by \\$k\\$ to get the answer.

Will time out on TIO for input greater than 8, but with infinite memory it would work for any input.

# Answer
> 8 votes
# PHP, 38 bytes

```
while(($n=decbin(++$x))%$argn);echo$n;

```

Try it online!

Counts up `n` in binary and divides it's decimal representation by `k` until there is no remainder; indicating the first, smallest multiple.

# Answer
> 7 votes
# T-SQL, 57 bytes

This script is really slow when using 18 as input

```
DECLARE @z INT = 18

DECLARE @ int=1WHILE
@z*@ like'%[^10]%'SET @+=1PRINT @z*@

```

# T-SQL, 124 bytes

T-SQL doesn't have binary conversion

This will execute fast:

```
DECLARE @ int=1,@x char(64)=0,@a int=2WHILE
@x%@z>0or @x=0SELECT
@x=left(concat(@%2,@x),@),@a-=1/~@,@=@/2-1/~@*-~@a
PRINT @x

```

**Try it online**

# Answer
> 7 votes
# Charcoal, 19 bytes

```
≔1ηＷ﹪ＩηＩθ≔⍘⊕⍘η²¦²ηη

```

Try it online! Link is to verbose version of code. Explanation:

```
≔1η

```

Start at `1`.

```
Ｗ﹪ＩηＩθ

```

Repeat until a multiple of `n` is found, treating the values as base 10.

```
≔⍘⊕⍘η²¦²η

```

Convert from base 2, increment, then convert back to base 2.

```
η

```

Output the result.

# Answer
> 7 votes
# Haskell, ~~44 38~~ 36 bytes

Saved two bytes by using `filter` as suggested by @ovs.

```
f k=filter(all(<'2').show)[0,k..]!!1

```

Try it online!

This checks all multiples of `k` and is slow for input 9 and 18.

I much prefer this version which defines the list of all "binary" numbers and searches for the first multiple of `k` among them. It quickly handles all test cases, but needs 52 bytes:

```
b=1:[10*x+d|x<-b,d<-[0,1]]
f k=[m|m<-b,mod m k<1]!!0

```

Try it online!

# Answer
> 6 votes
# Japt, ~~11~~ ~~9~~ 8 bytes

```
È*nvU}a¤

```

Try it

# Answer
> 6 votes
# Python 3.8 (pre-release),, ~~75~~\\$\cdots\\$ ~~50~~ 52 bytes

Saved 2 bytes thanks to Mukundan!!!
Added 2 bytes to fix error kindly pointed out by Giuseppe.

```
f=lambda k,n=1:(i:=int(f"{n:b}"))%k and f(k,n+1)or i

```

Try it online!

# Answer
> 6 votes
# Bash \+ Unix utilities, 52 bytes

```
for((n=1;n%$1;));do n=`dc<<<2dio1d$n+p`;done
echo $n

```

Try it online!

This counts in binary, views the resulting numbers in base 10, and stops when a multiple of the input is reached.

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

```
‘¡DṀḊƊ¿

```

**Try it online!**

### How?

Note that in Jelly empty lists are falsey, while other lists are truthy. Also dequeue, , is a monadic atom which removes the first item from a list, but when presented with only an integer Jelly will first convert that integer to a list by forming the range `[1..n]` thus  yields `[2..n]`.

```
‘¡DṀḊƊ¿ - Link: integer, k
      ¿ - while...
     Ɗ  - ...condition: last three links as a monad:
  D     -     decimal digits   e.g. 1410 -> [1,4,1,0]  or 1010 -> [1,0,1,0]
   Ṁ    -     maximum                       4                     1
    Ḋ   -     dequeue (implicit range of)   [2,3,4]               []
        -                                   (truthy)              (falsey)
 ¡      - ...do: repeat (k times):
‘       -     increment

```

For some reason, when the body of a while loop, `¿`, is a dyad each iteration sets the left argument to the result **and** then sets the right argument to the value of the left argument, so the 6 byte `+DṀḊƊ¿` does not work. (For example given `3` that would: test `3`; perform `3+3`; test `6`; perform `6+3`; test `9`; perform `9+6`; test `15`; perform `15+9`; etc...)

---

**Previous 8:**

```
DḂƑȧọð1#

```

(`DḂƑ` could be `DỊẠ` too.)

**An alternative 8**:

```
DṀ+%Ịð1#

```

# Answer
> 5 votes
# , ~~7~~ 6 bytes

-1 because I realized that W has operator overloading over `t`.

```
•B⌡≡kü

```

Uncompressed:

```
*Tt!iX*

```

repl.it is quite slow and you need to type in the program in code.w.

## Explanation

        % For every number in the range
    i   % from 1 to infinity:
     X  % Find the first number that satisfies
*       %     Multiply the current item by the input
 T      %     The constant for 10
  t     %     Remove all digits of 1 and 0 in the current item
        %     Both operands are converted to a string, just like in 05AB1E.
   !    %     Negate - checks whether it contains only 1 and 0.

      * % Multiply that result with the input (because it's the counter value).
```
</code></pre>

# Answer
> 5 votes
# Retina 0.8.2, 68 bytes

```
.+
$*1:1,1;
{`^(1+):\1+,(.+);
$2
T`d`10`.1*;
,0
,10
1+,(.+)
$1$*1,$1

```

Try it online! Somewhat slow so no test suite. Explanation:

```
.+
$*1:1,1;

```

Initialise the work area with `n` in unary, `k` in unary, and `k` in decimal.

```
{`^(1+):\1+,(.+);
$2

```

If `n` divides `k` then delete everything except the result. This causes the remaining matches to fail and eventually the loop exits because it fails to achieve anything further.

```
T`d`10`.1*;
,0
,10

```

Treat `k` as a binary number and increment it.

```
1+,(.+)
$1$*1,$1

```

Regenerate the unary conversion of `k`.

# Answer
> 5 votes
# Bash \+ Core utilities, 40 bytes

```
seq $1 $1 $[10**$1]|grep ^[01]*$|head -1

```

Try it online!

# Answer
> 4 votes
# Ruby, ~~42~~ ~~40~~ 36 bytes

```
->k{z=k;z+=k until z.digits.max<2;z}

```

Try it online!

Very slow for 18, but ultimately gets the job done.

4 bytes golfed down by G B.

# Answer
> 4 votes
# Java 10, ~~62~~ ~~59~~ 58 bytes

```
n->{var r=n;for(;!(r+"").matches("[01]+");)r+=n;return r;}

```

Try it online.

**Explanation:**

```
n->{             // Method with long as both parameter and return-type
  var r=n;       //  Result-long, starting at the input
  for(;!(r+"").matches("[01]+");)
                 //  Loop as long as `r` does NOT consists of only 0s and 1s
    r+=n;        //   Increase `r` by the input
  return r;}     //  After the loop is done, return `r` as result

```

This method above only works for binary outputs \\$\leq1111111111111111111\\$. For arbitrary large outputs - given enough time and resources - the following can be used instead (**~~99~~ ~~70~~ 64 bytes**):

```
n->{var r=n;for(;!(r+"").matches("[01]+");)r=r.add(n);return r;}

```

Try it online.

# Answer
> 4 votes
# Perl 5, 21 +2 (-ap) = 23 bytes

```
$_+=$F[0]while/[^01]/

```

Run with `-a` and `-p`, input to stdin. Just keeps repeatedly adding the input for as long as the result contains anything other than digits 0 and 1.

Try it online!

# Answer
> 4 votes
# C (gcc), 80 bytes

```
r,m,n;b(h){for(r=0,m=1;h;h/=2)r+=h%2*m,m*=10;h=r;}f(k){for(n=1;b(++n)%k;);b(n);}

```

This can probably be improved some but I have yet to find a way.

Converts the integer into binary and checks if it's a multiple.

Brute-force.

Try it online!

# Answer
> 4 votes
# , <sup>24</sup> <sup>23</sup> 22 bytes

```
+^:(0<10#@-.~&":])^:_~

```

Try it online!

Add the number to itself `+` while `^:...^:_` the following is true:

`(0<10#@-.~&":])` \- Something other than the digits 0 and 1 appear in the stringified number.

# Answer
> 4 votes
# Python 3, ~~50~~ 48 bytes

```
f=lambda k,n=0:n*({*str(n)}<={*"01"})or f(k,n+k)

```

Try it online!

## Explanation

* `n` represents the current multiple of `k`.
* `{*str(n)}<={*"01"}` checks if `n` only contains digits `0` or `1`. This is done by creating a set of characters of `n`, then checks if that set is a subset of \\$\\{0,1\\}\\$.
* `n*({*str(n)}<={*"01"}) or f(k,n+k)` is arranged such that the recursive call `f(k,n+k)` is only evaluated when `n` is 0 or `n` is not a binary multiple of `k`. Here multiplication acts as a logical `and`.

# Answer
> 3 votes
# Wolfram Language (Mathematica), 49 bytes

```
(x=#;While[Or@@(#>1&)/@IntegerDigits@x,x=x+#];x)&

```

Try it online!

# Answer
> 3 votes
# Burlesque, 13 bytes

```
rimo{>]2.<}fe

```

Try it online!

9 & 18 do work, but take a while because they're such large multiples. So I've taken them out of tests.

```
ri    # Read to int
mo    # Generate infinite list of multiples
{
 >]   # Largest digit
 2.<  # Less than 2
}fe   # Find the first element s.t.

```

# Answer
> 3 votes
# C# (Visual C# Interactive Compiler), ~~53~~ 49 bytes

<sup>turns out Max can cast chars to codes implicitly</sup>

I tried a recursive version, but it was longer. Can't think of a way to replace the loop with LINQ...

```
a=>{int r=a;while($"{r}".Max()>49)r+=a;return r;}

```

Try it online!

# Answer
> 3 votes
# MathGolf, 9 bytes

```
0ô+_▒╙2<▼

```

Try it online. (Test cases `n=9` and `n=18` are excluded, since they time out.)

**Explanation:**

```
0          # Start with 0
        ▼  # Do-while false with pop,
 ô         # using the following 6 commands:
  +        #  Add the (implicit) input-integer to the current value
   _       #  Duplicate it
    ▒      #  Convert it to a list of digits
     ╙     #  Pop and push the maximum digit of this list
      2<   #  And check if this max digit is smaller than 2 (thus 0 or 1)
           # (after the do-while, the entire stack joined together is output implicitly)

```

# Answer
> 3 votes
# Red, 52 bytes

```
func[n][i: 0 until[""= trim/with to""i: i + n"01"]i]

```

Try it online!

# Red, 54 bytes

```
func[n][i: 0 until[parse to""i: i + n[any["0"|"1"]]]i]

```

Try it online!

# Answer
> 3 votes
# Stax, 9 bytes

```
ü◘ø⌠Δ>0↔å

```

Port of my MathGolf answer. This is only my second Stax answer, so there might be a shorter alternative.

Try it online or try it online unpacked (10 bytes).

**Explanation (of the unpacked version):**

```
0             # Start at 0
 w            # While true without popping, by using everything else as block:
  x+          #  Add the input-integer
    c         #  Duplicate the top of the stack
     E        #  Convert it to a list of digits
      |M      #  Get the maximum of this list
        1>    #  And check that it's larger than 1
              # (after the while, the top of the stack is output implicitly as result)

```

# Answer
> 3 votes
# Icon, 50 bytes

```
procedure f(n)
i:=seq(n,n)&0=*(i--10)
return i
end

```

Try it online!

`seq(n,n)` generates an "infinite" (seq operator doesn’t work with large integers) sequence starting at `n` with step `n`

`&`is conjunction - Icon evaluates the next expression and if it fails, than backtracks to the expression to its left - so generates the next integer.

`i--10` finds the difference of the string representation of `i` with the string `10` \- Icon automatically casts number to strings when an operation on strings is used.

`*(1--10)` finds the length of the difference of `i` and `10` (which is a string)

`0=*(1--10)` \- if the length is `0`, the number is composed only of 1's and 0's.

# Answer
> 3 votes
# Husk, <sup>~~9~~</sup> 7 bytes

```
ḟoΛεd∫∞

```

Try it online!

-2 bytes from Leo.

# Answer
> 2 votes
# GolfScript, 31 bytes

```
:i;1{).{2 base}:b~{`+}*~i%}do b

```

Worked for 2-15 wen I tried them out, didn't bother doing more. May post explanation later, just wanted to get a brute submission down.

Try it online!

# Answer
> 2 votes
# Gaia, ~~10~~ 9 bytes

```
⟨:$2…⁻⟩+↺

```

Try it online!

```
		| implicit input, n
⟨     ⟩		| (1) monadic link:
 :$		| dup, and get decimal digits
   2…⁻		| remove all 1s and zeros
	↺	| if the result is truthy (non-empty)
       +	| add n and repeat from (1)
		| implicitly print result.

```

Times out on `n=9`...

# Gaia, 10 bytes

```
1⟨bdĖ⟩#ebd

```

Try it online!

Somewhat more interesting and also a lot faster; finds the first integer where: converting it to binary and interpreting as decimal digits are divisible by the input (and `ebd` converts it to the decimal form).

# Answer
> 2 votes
# Wolfram Language (Mathematica), 40 bytes

```
(For[x=#,Max@IntegerDigits@x>1,x+=#];x)&

```

Try it online!

## Ignoring maximum iteration limits, 37 bytes

```
#//.a_?(Max@IntegerDigits@#>1&):>a+#&

```

Try it online!

This will halt when the depth of 65536 is reached (i.e. if the result is larger than `65536 * (input)`).

# Answer
> 2 votes
# Pyth, 10 bytes

```
.Bf!%s.BTQ

```

Try it online!

`f`: Filter of all integers in increasing order, starting from an input of 1. Output the first matching input.

`.BT`: Convert the input to binary, as a string.

`s`: Convert the string to a base 10, as a integer.

`% ... Q`: Modulo the input

`!`: Boolean negation - returns true only if divisible.

`.B`: Convert the output of the filter back to a binary string and print it.

# Answer
> 2 votes
# JavaScript (Node.js), 50 bytes

```
(x,i=1,g=v=>v.toString(2))=>g(i)/x%1?f(x,++i):g(i)

```

Try it online!

# Answer
> 2 votes
# Roj, ~~178~~ ~~173~~ ~~171~~ ~~161~~ ~~160~~ ~~156~~ ~~153~~ ~~152~~ 141 bytes

Because I am completely new to Roj, there may still be potential golfs out here.

```
readint I;C=0;while 1 do
C=C+I;i=C;L=0<1;while i do
c=0;while c<=i/10 do
c=c+1
end;c=c-1;L=L and(i-10*c)<2;i=c
end;if L do
out C;halt
end
end

```

# Explanation

It's made primarily for me to find potential golfs.

Indented:

<pre><code>readint I; $ Take an input integer & save it into the variable I $
C = 0;     $ C: The counter that stores the current value $

while 1 do $ Forever: $

    C = C + I; $ Add the counter by the input $

    i = C; $ Copy the counter to a mutable variable $

    L = 0 < 1; $ Set the "Logic" variable to a truthy value $

               $ "0<1" is shorter than directly hard-coding "True", a 4-byte value $

    $ Check whether the input is made of 0 and 1 $

    $ This modifies the L variable $

    while i do $ Do the following "Scan" until we run out of digits $
        $ "Scan" over the input until we reach the end of the input $

        $ Current procedure: floor the value of the multiple / 10 $
        c = 0; $ Set the flooring result to the variable c $

        while c <= i / 10 do $ While the current counter is less $
                             $ than or equal to the multiple / 10 $
            c = c + 1        $ Increment the counter $
        end;
        c = c - 1;           $ Since we have one extra +1 to break $
                             $ out of the loop, we decrement the counter $

        L = L and (i - 10 * c)<2; $ Finally! Compare the currently-scanned $
                             $ number's equality with 1 or 0 $

        $ (i - 10 * c) Calculates i - 10 * (i // 10) $
        $ We already calculated (i // 10), $
        $ Hence the weird output expression $

        i = c                $ Divide the multiply by 10, floor that result $
    end;

    if L do         $ If this multiple is made of binary digits: $
        out C;      $ Output this multiple $
        halt        $ Stop the program $
    end
end
```

# Answer
> 1 votes
# SNOBOL4 (CSNOBOL4), ~~68~~ 55 bytes

```
	N =INPUT
A	X =X + N
	X NOTANY(10)	:S(A)
	OUTPUT =X
END

```

Try it online!

Adds `N` to `X`; if `X` contains any non-binary digits, repeat. Then print X.

# Answer
> 1 votes
# Jelly, 9 bytes

```
1BḌọɗ1#BḌ

```

Try it online!

A monadic link taking an integer \\$n\\$ and returning an integer.

Two bytes longer than @JonathanAllan’s solution, but a different approach so I still thought worth posting.

## Explanation

```
1   ɗ1#   | Starting with 1, find the first integer for which the following is true, using n as the right argument:
 B        | - Convert to binary
  Ḍ       | - Convert from decimal digits to integer
   ọ      | - Number of times divisible by n
       B  | Convert to binary
        Ḍ | Convert from decimal digits to integer

```

# Another alternative Jelly, 9 bytes

```
2*B€ḌọƇ⁸Ḣ

```

Try it online!

# Answer
> 1 votes
# Perl 6, 29 bytes

```
{first /^[0|1]+$/,(1..*X*$_)}

```

Try it online!

Find the first multiple of the input that is only composed of ones and zeroes

# Answer
> 1 votes
# C (gcc), ~~53~~ 48 bytes

```
n,m;F(k){for(n=m=k;m>1;m=m%10>1?n+=k:m/10);n=n;}

```

Try it online!

Explanation:

```
int F(int k)
{
    int n = k;
    int m = k;

    for (; m > 1;)
    {
        if (m % 10 > 1)     // no solution if least significant digit nether 0 nor 1. Try next multiple of k.
        {
            n += k;
            m = n;
        }
        else                // if the least significant digit is 0 or 1 divide by ten
        {
            m /= 10;
        }
    }

    return n;
}

```

Edit: removed return

# Answer
> 1 votes
# APL (Dyalog Unicode), 13 bytesSBCS

```
+⍣{∧/2>⍎¨⍕⍺}⍨

```

Try it online!

Straightforward algorithm: Repeat adding self until all digits are less than 2.

### How it works

```
+⍣{∧/2>⍎¨⍕⍺}⍨  ⍝ Input: n
+⍣{        }⍨  ⍝ Repeat adding n with starting value of n, until ... is true:
       ⍎¨⍕⍺    ⍝   Extract the digits
   ∧/2>        ⍝   All of the digits are less than 2

```

# Answer
> 1 votes
# Japt, 9 bytes

```
_%U}f_Ä ¤

```

Try it

# Answer
> 1 votes
# Python 2, 42 bytes

```
f=lambda k,n=0:max(`n`)!='1'and k+f(k,n+k)

```

Try it online!

A recursive function. We terminate when the maximum character of the string representation is `1`. We can't quite use `'<2'` instead because zero would trigger it, and we don't have a good way not to start at zero.

The larger outputs run out of recursion depth, at least with the default value. We'll also eventually get another issue with huge inputs when Python 2's backticks string representation appends an `L` for "long" to numbers starting with `2**63`, which will always be the maximum.

---

# Python 2, 42 bytes

```
n=k=input()
while'1'<max(`n`):n+=k
print n

```

Try it online!

A program, using a pretty straightforward loop.

# Answer
> 1 votes
# Haskell, 38 bytes

```
f x=filter(all(<'2').show)[x,x+x..]!!0

```

Try it online!

## Explanation

We make all the multiples of `x` with `[x,x+x..]`, filter them to contain only digits smaller than two `filter(all(<'2').show)` and then take the first one `!!0`

# Answer
> 1 votes
# Julia 1.0, 38 bytes

```
f(k,n=k)="10"⊇repr(n) ? n : f(k,n+k)

```

Try it online!

# Answer
> 1 votes
# Pip, ~~16~~ 12 bytes

```
TMXa<2a+:@ga

```

-4 bytes from Dlosc (removed unnecessary function)

The same general approach that most other answers are using: Loop until we reach a multiple that can also be a binary number. Takes very long for numbers \\$\>17\\$.

Try it online!

# Pip, 27 bytes

```
x:a
MN({a%x?0a}MTB,2**a)RM0

```

Converts all numbers till \\$2^n\\$ to binary and checks divisibility. Then removes all the 0's and gets the minimum. Takes very long for numbers \\$\>14\\$.

Try it online!

# Answer
> 1 votes
# PowerShell, 74 bytes

```
param($x)for(){$n=iex ([convert]::tostring(++$i,2));if(!($n%$x)){$n;exit}}

```

Try it online!

# Answer
> 1 votes
# PowerShell, 41 bytes

```
for(;++$n%"$args"-or$n-match'[2-9]'){}
$n

```

Try it online!

---

# PowerShell, 41 bytes

```
for(;++$n%"$args"-or$n-replace'0|1'){}
$n

```

Try it online!

# Answer
> 1 votes
# K (ngn/k), 17 bytes

```
{(|/1<10\)(x+)/x}

```

Try it online!

Sets up a straightforward while-over, seeded with `x`. Runs until `(|/1<10\)` returns `0` when executed on the result.

* `(...)(x+)/x` generate the next multiple of the original input, starting with the initial input
* `(|/1<10\)(...)/x` the condition tested after each iteration
    + `10\` convert to digits
    + `|/1<` check if any digit is larger than 1

# Answer
> 1 votes
# Thunno 2, 5 bytes

```
(G⁻;+

```

Try it online!

#### Explanation

```
(G⁻;+  # Implicit input
(  ;   # While loop
 G     # (condition)  Maximum of (implicit cast to digits of) top of stack
  ⁻    #              Decrement (i.e. not equal to one)
    +  # (body)  Add the input to the top of stack
       # Implicit output

```

# Answer
> 1 votes
# Vyxal, 38 bitsv1, 4.75 bytes

```
{:₀F|+

```

Try it Online!

Ports Thunno 2 but with fractional bytes.

## Explained

```
{:₀F|+
{   |   # While:
  ₀F    #   The numbers from 10 removed from
 :      #   A copy of the top of a stack is not empty
    |   # Do:
     +  #   Add the input to the top of the stack

 Created with the help of Luminespire at https://vyxal.github.io/Luminespire

```

# Answer
> 0 votes
# Python 3, 230 bytes

```
def f(n):
 s="1"
 while 2>1:
  if int(s)%n==0:
   return s
  if "0" in s:
   for j in range(0,len(s)):
    if s[j]=="0":
     q=j
   t=s[:q]
   for k in range(q,len(s)):
    t=t+str(1-int(s[k]))
   s=t
  else:
   s=str(10**len(s))

```

# Answer
> 0 votes
# Scala, 67 bytes

Port of @ovs's Python answer in Scala.

---

Try it online!

```
def f(k:Int,n:Int=0):Int=if(n>0&&n.toString.max<'2')n else f(k,n+k)

```

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


title: Check if a string is a shuffle of twins

text:
# Question
Title: Check if a string is a shuffle of twins
## Explanation

Two strings can be shuffled by interspersing their letters to form a new string, much like two piles of cards can be shuffled to form a single pile.

For example, the strings `HELLO` and `WORLD` can be shuffled to form `HWEOLRLLOD`, or `HEWORLLLDO`, or perhaps simply `HELLOWORLD`.

It is **not** a shuffle if the original order of letters is not preserved. For example, the `D` in `WORLD` cannot ever appear before the `R` after being shuffled. This means that `EHLLOWRDLO`, for instance, is not a shuffle of `HELLO` and `WORLD`, even though it contains all the original letters.

A string is a *shuffle of twins* if it can be formed by shuffling two identical strings. For example, `ABACBDECDE` is a shuffle of twins because it can be formed by shuffling `ABCDE` and `ABCDE`. `DBEACBCADE` is not a shuffle of twins because it cannot be formed by shuffling two identical strings.

## Program Details

Given an input string, output `0` if it is not a shuffle of twins, and output one of the twin strings if it is a shuffle of twins.

You may assume that the input string has a length inclusively between four and twenty characters and is composed entirely of uppercase alphabetic characters. It should be able to run in a reasonable amount of time, say, under 10 minutes.

This is code golf, so the shortest solution wins.

## Example I/O

```
> ABACBDECDE
ABCDE

> DBEACBCADE
0

> FFFFFF
FFF

> FFGGG
0

> ABBA
0

> AABB
AB

> AABAAB
AAB

```

I have an example (non-golfed) implementation.

# Answer
# Haskell, 114

```
main=getLine>>=putStrLn.f.p;f x=head$[a|(a,b)<-x,a==b]++["0"]
p[]=[([],[])];p(x:y)=do(a,b)<-p y;[(x:a,b),(a,x:b)]

```

**Ungolfed:**

```
main :: IO ()
main = getLine >>= putStrLn . findMatch . partitions

-- | Find the first partition where the two subsequences are
-- equal. If none are, return "0".
findMatch :: [(String, String)] -> String
findMatch ps = head $ [a | (a,b) <- ps, a == b] ++ ["0"]

-- | Return all possible partitions of the input into two
-- subsequences. Preserves the order of each subsequence.
--
-- Example:
-- partitions "AB" == [("AB",""),("B","A"),("A","B"),("","AB")]
partitions :: [a] -> [([a], [a])]
partitions []     = [([], [])]
partitions (x:xs) = do (a, b) <- partitions xs
                       [(x:a, b), (a, x:b)]

```

**Explanation:**

Most of the work is being done in the `partitions` function. It works by recursively generating all partitions `(a, b)` of the tail of the list, and then using the list monad to prepend the initial element `x` to each of them and gather all the results.

`findMatch` works by filtering this list so that only partitions where the subsequences are equal remain. It then returns the first subsequence in the first partition. If none remain, the list is empty, so the `"0"` appended at the end gets returned instead.

`main` just reads the input, feeds it through these two functions and prints it.
> 5 votes

# Answer
# R, 113 chars

```
l=length(x<-charToRaw(scan(,'')));max(apply(combn(l,l/2),2,function(i)if(all(x[i]==x[-i]))rawToChar(x[i])else 0))

```

Ungolfed (and instead a function that takes the string):

```
untwin <- function(x) {
  x <- charToRaw(x)
  indMtx <- combn(length(x),length(x)/2)
  res <- apply(indMtx, 2, function(i) {
    if (all(x[i]==x[-i]))
      rawToChar(x[i])
    else
      0
  })
  max(res)
}

untwin("ABACBDECDE") # "ABCDE"
untwin("DBEACBCADE") # 0

```

The solution relies on the `combn` function that generates all combinations of indices as columns in a matrix. `apply` then applies a function to each column (dimension `2`) in the matrix and returns a vector of strings or zeroes. `max` then find the biggest string (which trumps 0).

A cool feature in R is the ability to select a subset of a vector given a vector of indices, and to then select the *complement* of that subset by negating the indices: `x[i] == x[-i]`
> 4 votes

# Answer
## Mathematica, 87

This is directly based on hammar's post, but hopefully it is distinct enough to merit posting.

```
<<Combinatorica`

f=Catch[Cases[Characters@#~KSetPartitions~2,{x_,x_}:>Throw[""<>x]];0]&

```

Test:

```
f /@ {"ABACBDECDE", "DBEACBCADE", "FFFFFF", "FGG", "ABBA", "AABB", "AABAAB"}

```

```
{"ABCDE", 0, "FFF", 0, 0, "AB", "AAB"}
```
> 3 votes

# Answer
# Brachylog, 11 bytes

```
{;Ẹp}ᵐzcᵛ.∨

```

Try it online!

Using an unbound output variable as 0 might be cheating, so +1 byte if that's a problem (even though ideally it could just be allowed to fail and we could drop the `.∨`).

```
{   }ᵐ         For each character of the input,
 ;Ẹ            pair it with an empty string
   p           in either order.
      z        The zipped pairs
       cᵛ      concatenate to the same thing,
         .     which is output.
          ∨    If that's not possible, leave the output unbound instead of failing.

```
> 3 votes

# Answer
## D

```
string c(string in,string a=[],string b=[]){
    if(in.length==0)return a==b?a;"0";
    auto r=c(in[1..$],a~in[0],b);
    return r=="0"?c(in[1..$],a,b~in[0]):r;
}
void main(){writeln(c(readline));}

```

using depth first recursive search

I can make it faster with a `int i = min(a.length,b.length);if(a[0..i]!=b[0..i])return "0";` guard clause
> 1 votes

# Answer
### Ruby, 89 characters

```
s=->a,x,y{a=="\n"?x==y ?x:?0:[s[b=a[1..-1],x+c=a[0],y],s[b,x,y+c]].max}
$><<s[gets,'','']

```

This code implements a plain recursive search algorithm. The input must be given on STDIN.
> 1 votes

# Answer
## Perl, 68 chars

```
/^((.+)(?{local($x,$,)=($,,$x.$^N)}))+$(?(?{$o=$,eq$x&&$,})|x)/?$o:0

```

The input string assumed to be in the `$_` variable, the output is the value of the expression. Trailing newlines in input are ignored. You can run this from the command line like this:

```
perl -lne 'print /^((.+)(?{local($x,$,)=($,,$x.$^N)}))+$(?(?{$o=$,eq$x&&$,})|x)/?$o:0'

```

This code makes use of Perl's regexp engine (and specifically its embedded code execution feature) to do the backtracking. Basically, it matches the input string against the regexp `^((.+))+$`, keeping track of the odd- and even-numbered submatches in `$x` and `$,`, and rejecting the match at the end if the two aren't equal.
> 1 votes

# Answer
## Python, 168 characters

```
def f(s):
 c=s[0]
 d=i=r=0
 if s==c+c:r=c
 while i+1 and i<=len(s)/2 and not r:
  if i:d=f(s[1:i]+s[i+1:])
  if d:r=c+d
  i=s.find(c,i+1)
 return r
print f(raw_input())

```
> 1 votes

# Answer
# 05AB1E, 11 bytes

```
.œ€ιJ.ΔË}θ<

```

Try it online or verify all test cases.

If a more flexible output would have been allowed which outputs `-1` instead of `0`, and `["ABCDE","ABCDE"]` instead of `"ABCDE"`, it could have been **8 bytes** instead:

```
.œ€ιJ.ΔË

```

Try it online or verify all test cases.

**Explanation:**

```
.œ         # Get all partitions of the (implicit) input-string
           #  i.e. "AABB" → [["A","A","B","B"],["A","A","BB"],["A","AB","B"],["A","ABB"],
           #   ["AA","B","B"],["AA","BB"],["AAB","B"],["AABB"]]
  €ι       # Uninterleave each partition
           #  → [[["A","B"],["A","B"]],[["A","BB"],["A"]],[["A","B"],["AB"]],[["A"],["ABB"]],
           #   [["AA","B"],["B"]],[["AA"],["BB"]],[["AAB"],["B"]],[["AABB"],[]]]
    J      # Join the inner lists together to a single string
           #  → [["AB","AB"],["ABB","A"],["AB","AB"],["A","ABB"],
           #   ["AAB","B"],["AA","BB"],["AAB","B"],["AABB",""]]
     .Δ    # Find the first result for which:
           # (will result in -1 if none are valid)
       Ë   #  Both strings are equal, thus a twin
      }θ   # Afterwards, only leave the last value (the single string if we've found a
           # twin; or 1 if it resulted in -1)
           #  i.e. ["AB","AB"] → "AB"
           #  i.e. -1 → 1
        <  # And decrease by 1 (no-op if it was a string with just uppercase letters)
           #  i.e. "AB" → "AB"
           #  i.e. 1 → 0
           # (after which the result is output implicitly)

```
> 1 votes

# Answer
# JavaScript (Node.js), 54 bytes

```
g=([c,...x],p,q)=>c?g(x,[p]+c,q)||g(x,[q]+c,p):p==q&&p

```

Try it online!

Try each split
> 1 votes

# Answer
# Scala, 431 bytes

431 bytes, it can be golfed much more.

---

Golfed version. Try it online!

```
def g(n:Int)={
def l(n:Int,r:Int):ArrayBuffer[List[Int]]=if(r==0)ArrayBuffer(List())else if(r==n)ArrayBuffer((0 until n).toList)else l(n-1,r-1).map(n-1::_)++l(n-1,r)
l(n,n/2)}
def u(s:String)={
val l=s.length
if(l%2!=0)"0"
else{
val c=g(l)
var r="0"
var m=0
for(b<-c){
val i=b.toSet
val a=(0 until l).filterNot(i)
val h=i.toList.sorted.map(s.charAt)
val d=a.sorted.map(s.charAt)
if(h==d&&h.length>m){
m=h.length
r=h.mkString
}}
r}}

```

Ungolfed version. Try it online!

```
import scala.collection.mutable.ArrayBuffer

object Main {

  def getCombinations(n: Int): ArrayBuffer[List[Int]] = {
    def loop(n: Int, r: Int): ArrayBuffer[List[Int]] = {
      if (r == 0) ArrayBuffer(List())
      else if (r == n) ArrayBuffer((0 until n).toList)
      else loop(n - 1, r - 1).map(n - 1 :: _) ++ loop(n - 1, r)
    }

    loop(n, n / 2)
  }

  def untwin(s: String): String = {
    val length = s.length
    if (length % 2 != 0) {
      return "0"
    }

    val combinations = getCombinations(length)

    var result: String = "0"
    var maxLen = 0
    for (comb <- combinations) {
      val i = comb.toSet
      val rest = (0 until length).filterNot(i)
      val firstHalf = i.toList.sorted.map(s.charAt)
      val secondHalf = rest.sorted.map(s.charAt)
      if (firstHalf == secondHalf && firstHalf.length > maxLen) {
        maxLen = firstHalf.length
        result = firstHalf.mkString
      }
    }

    result
  }

  def main(args: Array[String]): Unit = {
    println(untwin("ABACBDECDE")) // "ABCDE"
    println(untwin("DBEACBCADE")) // "0"
    println(untwin("FFFFFF")) // "FFF"
    println(untwin("FFGGG")) // "0"
    println(untwin("ABBA")) // "0"
    println(untwin("AABB")) // "AB"
    println(untwin("AABAAB")) // "AAB"
  }
}

```
> 0 votes

---
Tags: code-golf, string, decision-problem
---


title: Rearrange to a palindrome

text:
# Question
Title: Rearrange to a palindrome
Given a string, shuffle it so that it becomes a palindrome.

For example, `adadbcc` can be arranged into `dacbcad`, or `dcabacd`, `acdbdca` and more. Any of these (or all) is acceptable, and duplicates are allowed if outputting all. Something like `abc` cannot be shuffled into a palindrome, and you can assume it won't be inputted.

(if it helps) input will only contain lowercase letters.

## Testcases

These show one possible solution.

```
nanas -> nasan
coconutnut -> conuttunoc
apotato -> atopota
manplancanalpanamaaaa -> amanaplanacanalpanama
canadadance -> canadedanac
nananana -> nanaanan
anaan -> anana

```

# Answer
# Brachylog, 3 bytes

```
p.↔

```

Try it online!

Also acts as a generator for all possible outputs.

### Explanation

```
p.         The output is a permutation of the input
 .↔        The output reversed is itself

```
> 13 votes

# Answer
# , 21 bytes

```
(,~`,/@/:2|1#.e.)@/:~

```

Try it online!

A non brute force approach which runs in n\*log(n) time.

* `/:~` Sort. This ensures that like elements are grouped together.
* `/:2|1#.e.` Then sort by number of occurrences, modded by 2. This puts any items with an odd number of elements at the end of the array, while keeping like elements together.
* `,~`,/@` Reduce that from the right by alternately appending and prepending elements. The upshot is that we start with the middle element, and then build outward by adding pairs of elements to opposite sides.
> 10 votes

# Answer
# Python 3, 72 bytes

```
*r,=s={''}
for c in input():s^={c};r+={c}-s
print(*r,*s,*r[::-1],sep="")

```

Try it online!

Saved 2 bytes by pxeger and xnor. It could be 66 bytes as xnor pointed out if output as list of characters.

It is \\$O(n)\\$.
> 8 votes

# Answer
# 05AB1E, 4 bytes

```
œʒÂQ

```

Try it online!

# Explanation

```
œ          all permutations of the (implicit) input
ʒ          only keep those such that
 Â         push x, reversed(x)
 Q         they are equal

```
> 6 votes

# Answer
# JavaScript (Node.js), 69 bytes

```
a=>[...p=a.filter(c=>!(a[c]^=1)),...a.filter(c=>a[c]),...p.reverse()]

```

Try it online!

---

# JavaScript (Node.js), 78 bytes

```
f=(s,c='',r=s.replace(/^(.)(.*)\1|./,'$2'),t=RegExp.$1)=>s?t+f(r,t?c:s[0])+t:c

```

Try it online!

Input / Output as strings.
> 6 votes

# Answer
# Python, 67 bytes

```
lambda x:(s:=sorted(x,key=lambda e:(x.count(e)%2,e)))[1::2]+s[::-2]
```

Attempt This Online!

Port of Jonah's excellent J solution.
> 6 votes

# Answer
# C (gcc), ~~124~~ ~~108~~ 107 bytes

*16 bytes saved thanks to c--! 1 byte saved thanks to ceilingcat!*

```
f(c,n,i,j,k)char*c;{for(i=j=0;i<n;i++)j=*c-c[i]?j:i;k=c[i=j?n--,n--:i/2];
c[i]=c[j];c[j]=k;n>2&&f(c+!!j,n);}

```

Try it online! Linebreak added for clarity. Function `f` which takes as input a pointer to the start of a `char` array and its length as `n`. Modifies the input array in place, yielding a single result.

Annoying that I can't save a few bytes by using `c[i]^=c[j]^=c[i]^=c[j]` instead of a standard switch, but this expression fails when `i == j`, and accounting for that doesn't end up saving any bytes.

## Commented explanation

*Slightly outdated, but the same general concept is the same. In the current version, we infer the count by observing that `k` is 1 if and only if `j` is 0.*

```
f(c,n,i,j,k,t) char*c; {
    // count the number of instances of the first character, *c
    for(i = k = 0; i < n; i++)
        // if we found *c in the string
        *c == c[i]
            ? k++, j = i // then note it in our tally, and note its index as j
            : 0;         // else do nothing

    // i is now the original length n
    // j is now the index of the last occurrence of *c

    // we will check if there is more than one occurrence of *c
    --k
        // this is truthy iff k > 1. in this case, we set up further recursion
        ? n -= 2,   // deduct the two solved characters from the solve length
          i--       // we want to swap with the end of the string (i=n-1)
        // else, if k == 1, then we need to put this character in the middle
        // to properly palindromize it
        : (j = 0,   // we want to swap the lone character (at j=0)
           i /= 2); // with the center character (at i=n/2).

    // swap characters at positions j and i
    // when k>1,  swaps the last occurrence of *c with the end of the string
    // when k==1, swaps the first character with the middle of the string
    t = c[i];
    c[i] = c[j];
    c[j] = t;

    // if n < 2, the string is solved
    // otherwise, we will recurse as follows:
    //  - when k was initially >1, k is now k-1, and !!k evaluates to 1,
    //    letting us recurse starting with c+1.
    //    in this case, n is now n-2, letting us recur on the string without
    //    the bookending characters
    //  - when k was initially 1, k is now 0, and !!k evaluates to 0.
    //    this means we recurse with c, and examine the character we
    //    just swapped there. n is also unchanged in this branch.
    //    furthermore, this swap only ever happens once because
    //    we check n > 2 before attempting to recurse.
    n > 2 && f(c + !!k, n);
}

```
> 5 votes

# Answer
# lin, 19 bytes

```
`perm".+ `rev `="`?

```

Try it here!

For testing purposes (use `-i` flag if running locally):

```
"nanas" ; `_
`perm".+ `rev `="`?

```

## Explanation

Prettified code:

```
`perm (.+ `rev `= ) `?

```
* ``perm` permutations
* `(...) `?` find first...
    + `.+ `rev `=` palindrome
> 4 votes

# Answer
# Python, 120 bytes

```
lambda a,j="".join:[C:=Counter(a),x:=j(C[c]//2*c for c in C)][1]+j(C[c]%2*c for c in C)+x[::-1]
from collections import*
```

Attempt This Online!

There's probably a much shorter way to do this in \\$ O(n!n) \\$ time or something silly like that, but this is linear I think.

# Python, 94 bytes

```
lambda a,j="".join:(x:=j(a.count(c)//2*c for c in{*a}))+j(a.count(c)%2*c for c in{*a})+x[::-1]
```

Attempt This Online!

A little shorter, but runs in \\$ O(n^2) \\$ time.
> 4 votes

# Answer
# Vyxal, 4 bytes

```
Ṗ'Ṙ=

```

Try it Online! Outputs all possibilities with duplicates. Add `;U` to remove them. Takes permutations and only keeps those that are equal after reversal.
> 3 votes

# Answer
# Curry (PAKCS), 41 bytes

```
f a@([]?[_])=a
f(a:b++a:c)=a:f(b++c)++[a]

```

Try it online!

This may returns multiple results, with duplicates, but not necessarily all of them. If this is not allowed, you can add the flag `:set +first` to print only the first result: Try it online!.
> 3 votes

# Answer
# Prolog (SWI), 35 bytes

```
X+P:-permutation(P,X),reverse(P,P).

```

Try it online!

Prolog is perfect for this. I/O as a list of char codes (or list of atoms or list of strings, doesn't matter).

If there are multiple solutions, each solution is its own choice point (may contain duplicates): Try it online! If there are none, the goal will simply fail.

In fact, the first argument doesn't even have to be instanciated. If you run with both non-initialized, the first one will just infinitely produce all possible ways to arrange variables in a list where it is possible to rearrange to a palindrome, and the second one will be it rearranged to a palindrome.

You can even do the reverse operation - given a palindromic string for the output, it will give all inputs that will produce that output. Try it online!
> 3 votes

# Answer
# Ruby, 41 bytes

```
->a{a.permutation.select{_1==_1.reverse}}
```

Attempt This Online!

Inputs and outputs array of chars. Output contains all answers with duplicates, but test suite prints only the first one, so that it doesn't flood the output.
> 2 votes

# Answer
# Wolfram Language (Mathematica), 33 bytes

```
Select[PalindromeQ]@*Permutations

```

Try it online!

-1 byte thanks to att
> 2 votes

# Answer
# Alice, 19 bytes

```
/@P?w$.R/
\IO>K.-!\

```

Try it online!

```
/IP>w..!R-$K?O@      Full program
/                    Switch to ordinal mode
 IP                  Read the input and generate all the possible permutations
   >w     $K         For each permutation
      .!             Store a copy of the permutation on the tape
     .  R            Reverse the permutation
         -           Subtract the reversed permutation from the permutation (leaving "" if it is a palindrome, exiting the loop)
            ?O@      Print the tape

```
> 2 votes

# Answer
# Nekomata, 4 bytes

```
↕:↔=

```

Attempt This Online!

A port of @Fatalize's Brachylog answer.

```
↕:↔=
↕       Permutation
 :      Duplicate
  ↔     Reverse
   =    Check equality

```

Returns all solutions with duplicates. You can add the `-1` flag to print only the first solution.
> 2 votes

# Answer
# Factor \+ `math.combinatorics`, <sup>~~41~~</sup> 38 bytes

```
[ [ dup reverse = ] find-permutation ]

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES6),  ~~63~~  62 bytes

Expects and returns a string.

```
f=s=>s==(S=s.replace(/(.)(.*)\1/,(_,A,B)=>(s=A,B)))?s:s+f(S)+s

```

Try it online!

### Commented

```
f =              // f is a recursive function
s =>             // taking the input string s
s == (           // test whether s is unchanged
  S = s.replace( // when turned into the reduced string S
                 // obtained by looking in s for:
    /(.)(.*)\1/, //   a character A, followed by some string B
                 //   (which may be empty), followed by A
    (_, A, B) => //   if found,
      (s = A, B) //   copy A into s and replace the match with B
  )              //   (i.e. both instances of A are removed)
) ?              // if S is equal to s:
  s              //   we're left with either an empty string or a
                 //   single character; either way, this ends up
                 //   in the middle of the output
:                // else:
  s + f(S) + s   //   append s, followed by the result of a
                 //   recursive call with S, followed by s again

```
> 1 votes

# Answer
# Perl 5 `-F` , 57 bytes

```
$_=join"",sort@F;s/(.)\1/!push@r,$1/ge;say@r,$_,reverse@r

```

Try it online!
> 1 votes

# Answer
# Haskell, 52 bytes

```
import Data.List
find(\x->x==reverse x).permutations

```

Try it online!

Pretty new to Haskell so I'm very open to suggestions on how this could be improved, because I have a feeling it can be a lot - especially concerning that lambda, but I couldn't find how to make it pointfree.
> 1 votes

# Answer
# APL (Dyalog Classic), 19 bytes

```
{⌊/⍵=⌽⍵:⍵⋄∇⍵[?⍨≢⍵]}

```

Try it online!

**Usage:**

```
      palindrome←{⌊/⍵=⌽⍵:⍵⋄∇⍵[?⍨≢⍵]}
      palindrome 'baba'
baab
      palindrome 'daabbcc'
cbadabc

```
> 1 votes

# Answer
# J-uby, 27 bytes

Port of Kirill L.’s Ruby answer.

```
:permutation|:select+:==%:~

```

Attempt This Online!
> 1 votes

# Answer
# Japt, 5 bytes

Outputs all possibilities. Replace `f` with `æ` to output just 1.

```
á fêQ

```

Try it
> 1 votes

# Answer
# Retina, 35 bytes

```
O`.
|""L^`((.)\2)*.?
$
$^$`
(.).
$1

```

Try it online! Link includes test cases. Explanation: Based on @Jonah's J solution.

```
O`.

```

Sort the characters into order.

```
|""L^`((.)\2)*.?

```

If there's an odd character, split the string after that point and exchange (`^`) and join (`|""`) the two halves. (There's also an empty string in the results but obviously it doesn't have any effect.)

```
$
$^$`

```

Append the reverse of the string.

```
(.).
$1

```

Drop every other character.
> 0 votes

# Answer
# Charcoal, 24 bytes

```
≔Φθ﹪№…θκι²ηηΦΦθ﹪№θι²¬κ⮌η

```

Try it online! Link is to verbose version of code. Explanation:

```
≔Φθ﹪№…θκι²ηη

```

Using my code from Generate an arbitrary half of a string, extract half (rounded down) of the characters from the string, but also save it in a variable.

```
ΦΦθ﹪№θι²¬κ

```

If there was a character that appeared an odd number of times then output it. (Now if only `Maximum("")` returned the empty string...)

```
⮌η

```

Output the reverse of the half string.
> 0 votes

# Answer
# x86-64 machine code, 31 bytes

```
31 C9 FF CA AC 0F BB C1 73 FA 88 04 17 AA 83 EA 02 77 F1 75 09 0F BC C1 75 01 AC 0C 60 AA C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes the address of the input, as an array of single-byte characters, in RSI and its length in RDX, and takes in RDI an address at which to place the result, as a non-overlapping array of single-byte characters of the same length.

Part of this is similar to my answer to "Generate an arbitrary half of a string".

In assembly:

```
f:
    xor ecx, ecx    # Set ECX to 0.
    dec edx         # Subtract 1 from the length in EDX.
repeat:
    lodsb           # Load a byte from the string into AL, advancing the pointer.
    btc ecx, eax    # Invert the bit in ECX indexed by the low 5 bits of that byte.
                    #  Set CF to the previous value of that bit.
    jnc repeat      # Jump back if CF is 0.
    mov [rdi+rdx], al   # Place the byte at a position that starts from the end of
                        #  the output string and will move backwards.
    stosb           # Add it to the start of the output, advancing the pointer.
    sub edx, 2      # Subtract 2 from EDX. (= # of unfilled places - 1)
    ja repeat       # Jump back if it is still positive.
    jnz end         # Jump if it is -1 (all places filled: happens for even length).
    bsf eax, ecx    # Set EAX to the index of the 1 bit in ECX.
                    # (If the input is valid, there is at most one 1 bit here.)
    jnz skip        # Jump if there was a 1 bit in ECX.
    lodsb           # (Otherwise, the final instance of the odd-count character
                    #  is at the end of the string and has not yet been read.)
                    # Load a byte from the string into AL, advancing the pointer.
skip:
    or al, 0x60     # Set bits 5 and 6 in AL, making the correct lowercase letter.
    stosb           # Add it to the output (in the centre), advancing the pointer.
end:
    ret             # Return.

```
> 0 votes

# Answer
# JavaScript (SpiderMonkey), 55 bytes

```
g=a=>a+''==a.reverse()?a:g(a.sort(_=>Math.random()<.5))

```

Try it online!

Shuffle until meet requirement
> 0 votes

# Answer
# Scala, 58 bytes

Golfed version. Try it online!

```
_.toSeq.permutations.map(_.mkString).find(x=>x==x.reverse)

```

Ungolfed version. Try it online!

```
object Main {

  def permutations(s: String): List[String] =
    if (s.length == 1) List(s)
    else s.toList.permutations.map(_.mkString).toList

  def palindromePermutations(s: String): Option[String] =
    permutations(s).find(x => x == x.reverse)

  def main(args: Array[String]): Unit = {
    val words = List("nanas", "coconutnut", "apotato", "canadadance", "nananana", "anaan")
    words.map(palindromePermutations).foreach {
      case Some(palindrome) => println(palindrome)
      case None => println("None")
    }
  }
}

```
> 0 votes

---
Tags: code-golf, string, balanced-string, palindrome
---


title: How many 1's we get

text:
# Question
Title: How many 1's we get
## Description

Count how many occurrences there are of the digit **1** between two given numbers \\$\[a, b\]\\$, inclusive.

For example, from 1 to 100 it should be 21:

**1**, **1**0, **11**, **1**2, **1**3, **1**4, **1**5, **1**6, **1**7, **1**8, **1**9, 2**1**, 3**1**, 4**1**, 5**1**, 6**1**, 7**1**, 8**1**, 9**1**, **1**00

The number **1** is repeated 21 times.

## Rules

1. Each number in the input list is guaranteed is an integer in the range \\$0 \leq a \leq b \< 2^{32}\\$.
2. The shortest answer in bytes wins.

## Test cases

```
[1, 100] -> 21
[11, 200] -> 138
[123, 678] -> 182

```

## Example

Here is my code using bash

```
eval echo {$1..$2}|grep -o 1|wc -l

```

# Answer
> 10 votes
# 05AB1E, ~~5~~ 4 bytes

Thanks a lot to OP! Now I can save a byte

```
ŸSΘO

```

Try it online!

## Explanation

```
Ÿ    Inclusive range
 S   Split the string into individual chars
  Θ  (Vectorizes) Does this character == "1"?
   O Sum the resulting list

```

# Answer
> 8 votes
# Python 2, ~~39~~ 36 bytes

-3 bytes thanks to @SurculoseSputum

```
lambda a,b:`range(a,b+1)`.count('1')

```

Try it online!

# Python 3, ~~42~~ 40 bytes

-2 bytes thanks to @JoKing

```
lambda a,b:f"{*range(a,b),b}".count('1')

```

Try it online!

# Answer
> 7 votes
# Rust+itertools, 42 bytes

```
|a,b|(a..=b).join("").matches('1').count()

```

Try it in the Rust Playground!

# Answer
> 6 votes
# APL (Dyalog Extended), 9 bytes

```
+/'1'=⍕⍤…

```

Try it online!

`+/` sum

`'1'=` where the character is equal to

the string representation

of

the range

# Answer
> 6 votes
# Java 8, ~~71~~ ~~67~~ 66 bytes

```
a->b->{var s="";for(;b>=a;)s+=b--;return~-s.split("1",-1).length;}

```

-4 bytes thanks to *@OlivierGrégoire*.

Try it online.

**Explanation:**

```
a->b->{                // Method with two integer inputs and integer return-type
  var s="";            //  String `s`, starting empty
  for(;b>=a;)          //  Loop `b` downwards in the range [`b`, `a`]:
    s+=b--;            //   And append `b` to to String `s`
  return~-s.split("1", //  Split String `s` on "1",
                  -1)  //  and keep empty trailing items
           .length;    //  Then get the amount of parts of this array
                       //  And decrease it by 1 with `~-`, before turning it as result

```

# Answer
> 6 votes
# Octave, ~~29~~ ~~28~~ 27 bytes

```
@(x,y)sum(mat2str(x:y)==49)

```

Try it online!

# Answer
> 5 votes
# , 43 bytes

```
function(x,y)sum(unlist(gregexpr(1,x:y))>0)

```

Try it online!

# Answer
> 4 votes
# Ruby, 62 46 28 bytes

```
->c,d{[*c..d].join.count ?1}

```

-18 bytes, courtesy of Dingus.

Try it online!

# Answer
> 4 votes
# Retina 0.8.2, ~~36~~ 32 bytes

```
\d+
$*_
(?<=(_+) _*)(?=\1)
$.'
1

```

Try it online! Link includes test cases. Explanation:

```
\d+
$*_

```

Convert `a` and `b` to unary, but use `_` instead of `1` to avoid confusion. (In Retina 1 this would just be `*`, saving 2 bytes.)

```
(?<=(_+) _*)(?=\1)
$.'

```

At each boundary in `b` up to and including `a` from the end, insert the distance to the end in decimal, thus generating the range from `b` down to `a`.

```
1

```

Count the resulting number of `1`s.

# Answer
> 4 votes
# JavaScript (ES6), 44 bytes

Expects `(a)(b)`.

```
a=>g=b=>b<a?0:(b+g).split(1).length-3+g(b-1)

```

Try it online!

### How?

We use a recursive function `g` to count how many `1`'s we have in `b` and decrement `b` until it's lower than `a`.

In order to count the `1`'s, we have to coerce `b` to a string. We could do `b+''` but it's shorter to use `b+g`. Because the source code of `g` itself contains two `1`'s, we subtract `3` instead of just `1` from the result of `(b+g).split(1).length`.

# Answer
> 4 votes
# Google Sheets, 68

```
=SUM(ArrayFormula(LEN(REGEXREPLACE(""&SEQUENCE(A2-A1+1,1,A1),"[^1]",

```

Sheets auto-closes parens.

This is super slow at large ranges, but as this is Code Golf, we're here to optimize character count. My first attempt was to use `JOIN(SEQUENCE(...))` to make one long string then count the 1's, but as it turns out, Sheets has a limit of 50000 characters, so that didn't work.

# Answer
> 4 votes
# Kotlin, 49 bytes

```
{x:Int,y:Int->(x..y).sumBy{"$it".count{it=='1'}}}

```

Try it online!

# Answer
> 4 votes
# Haskell, 26 bytes

```
a!b=sum[1|'1'<-show[a..b]]

```

Try it online!

# Answer
> 3 votes
# MathGolf, 8 bytes

```
↨æ▒m┴Σ]Σ

```

Try it online.

**Explanation:**

```
↨         # Loop in the range [a,b] using the two implicit inputs a,b,
 æ        # and execute the following four commands:
  ▒       #  Convert the integer to a list of digits
   m      #  Map over each digit:
    ┴     #   And check which are equal to 1 (1 if 1; 0 otherwise)
     Σ    #  Get the sum of those checks
      ]   # After the loop, wrap all values on the stack into a list
       Σ  # And sum this list
          # (after which the entire stack joined together is output implicitly as result)

```

# Answer
> 3 votes
# PHP, ~~46~~ 45 bytes

```
fn($a,$b)=>substr_count(join(range($a,$b)),1)

```

Try it online!

# Answer
> 3 votes
# Perl 5 `-p`, 21 bytes

```
map$\+=y/1//,$_..<>}{

```

Try it online!

# Answer
> 3 votes
# PowerShell, 40 bytes

```
$a,$b=$args
($a..$b|sls 1 -a|% m*).Count

```

Try it online!

---

# PowerShell, 40 bytes

```
($args-join'..'|iex|sls 1 -a|% m*).Count

```

Try it online!

# Answer
> 3 votes
# C (gcc), 58 bytes

```
i;c;f(a,b){for(c=0;b/a;)for(i=a++;i;i/=10)c+=i%10==1;a=c;}

```

Try it online!

# Answer
> 3 votes
# Factor, 65 bytes

```
: f ( a b -- n ) [a,b] [ number>string [ 49 = ] count ] map sum ;

```

Try it online!

# Answer
> 3 votes
# K (oK), ~~19~~ 17 bytes

**Solution:**

```
{+/"1"=,/$x_!1+y}

```

Try it online!

**Explanation:**

Range generation is inefficient (i.e. generate range 0..Y and then drop from front, rather than generating range X..Y) but saves 2 bytes.

```
{+/"1"=,/$x_!1+y} / the solution
{               } / lambda taking implicit x & y args
             1+y  / add 1 to y
            !     / range 0..N
          x_      / drop (_) x items from front
         $        / convert to string
       ,/         / flatten
   "1"=           / is string equal to "1"?
 +/               / sum

```

# Answer
> 3 votes
# , ~~19~~ 16 bytes

-3 bytes thanks to Jonah!

```
1#.1=/&":[,-.&i.

```

Try it online!

# Answer
> 3 votes
# JavaScript (ES6), ~~63~~ 62 bytes

```
a=>b=>([...Array(b-a+1)].map((_,i)=>i+a)+'').split(1).length-1

```

Try it online

```
[...Array(b-a+1)] // an array of length b-a+1
map((_,i)=>i+a)   // fill it with numbers from a to b
+''               // convert it to a string with each number separated by a comma
.split(1)         // split at each 1
.length-1         // count the chunks and subtract 1

```

-1 byte thanks to @Jo King

# Answer
> 2 votes
# Japt, 5 bytes

The spec contradicts itself as to whether the range should be inclusive or not. If it shouldn't then replace `õ` with `o`.

```
õ ¬è1

```

Try it

# Answer
> 2 votes
# Rust, 63 bytes

```
|a,b|(a..=b).map(|x|format!("{}",x).matches('1').count()).sum()

```

Try it online!

# Answer
> 2 votes
# MATL, 7 bytes

```
&:V1V=s

```

Try it online!

## Explanation

```
&:V1V=s
     =s  % Count occurrences
   1V    % of '1' in
  V      % string of
&:       % inclusive range of input

```

# Answer
> 2 votes
# Pyth, ~~8~~ 7 bytes

-1 byte thanks to @FryAmTheEggman

```
/`}QE"1

```

Try it online!

## Explanation

```
/`}QE"1
  }QE     # Inclusive range on input
 `        # string of the range ([1, 2, 3] -> "[1, 2, 3]")
/    "1   # count ones

```

# Answer
> 2 votes
# Scala, ~~29~~ 21 bytes

```
_.to(_)+""count(49==)

```

Try it online!

# Answer
> 2 votes
# Java (OpenJDK 8), 80 bytes

```
a->b->IntStream.range(a,b+1).flatMap(i->(""+i).chars()).filter(x->x==49).count()

```

Try it online!

Doesn't need much of an explanation, but here's one anyways:

```
Function<Integer, Function<Integer, Long>> f =
    a -> b->
      IntStream
        .range(a,b+1) //Create an IntStream going from a to b
        .flatMap(i -> //Map every int i in that stream
          (""+i)      //Make it a string
          .chars()    //Turn that string to an IntStream
        )    //Flatten that
        .filter(x -> x == 49)  //Keep all the '1's
        .count();              //Find out how many '1's there are

```

# Answer
> 2 votes
# Jelly, 5 bytes

```
rDFċ1

```

Try it online!

**Explanation:**

```
rDFċ1
r      range of the inputs
 DF    make decimal and flatten; list of all the digits in the range
   ċ1  count occurences of 1

```

# Answer
> 2 votes
# Wolfram Language (Mathematica), 29 bytes

```
Tr@DigitCount[Range@##,10,1]&

```

Try it online!

# Answer
> 2 votes
# Dart, 56 bytes

```
f(a,b)=>'1'.allMatches([for(;a<=b;a++)a].join()).length;

```

Try it online!

# Answer
> 2 votes
# Arn, ~~18~~ 14 bytes

```
÷|Ë¶‘○Øî9þæEƥ"

```

# Explanation

Unpacked:

```
+\${=1}((1=>):|c

```

Ungolfed:

```
+\ Fold with addition
  ${ Filter with block
    =1 Equals one
  }
  (
    (
      1=> Range [1, in]
    )
    :| c Join with no separator
  ) Implicit, can be removed

```

Strings automatically coerced into array context, output implicit

# Answer
> 2 votes
# \>\<\>, 44 bytes

```
|>:a%:1=&+&/&0
v&n;>~1+::{:})?!
>v,a^!?)0:-\

```

The wrong tool for the job, as \>\<\> knows nothing about decimal notation.

Takes (b,a) on the stack.

# Answer
> 2 votes
# Lua, 63 bytes

```
c,a,b=0,...for i=a,b do c=c+({('').gsub(i,1,0)})[2]end print(c)

```

Try it online!

Apparently, we can't use `...` as a range for `for`. What a shame.

# Answer
> 2 votes
# Pip, 8 bytes

```
1NSTa\,b

```

Inclusive range of a and b, converts to string, find number of 1's.

Try it online!

# Answer
> 2 votes
# Husk, 5 bytes

```
#1ṁd…

```

Try it online!

Jelly, but reversed.

# Answer
> 2 votes
# Japt, 6 bytes

```
õV ¬è1

```

Try it here

# Answer
> 1 votes
# Io, 78 bytes

Just generates a range, and then counts the occurances of `1`'s.

```
method(a,b,Range 1 to(b)asList select(i,i>=a)join asList select(i,i=="1")size)

```

Try it online!

# Answer
> 1 votes
# Charcoal, 9 bytes

```
Ｉ№⪫…·ＮＮω1

```

Try it online! Link is to verbose version of code. Explanation:

```
      Ｎ     First input as a number
     Ｎ      Second input as a number
   …·       Inclusive range
  ⪫    ω    Cast to string and join
 №      1   Count literal `1`s
Ｉ           Cast to string
            Implicitly print

```

# Answer
> 1 votes
# Gaia, 6 bytes

```
U$¦_1C

```

Try it online!

```
U	| Inclusive range [a,b]
$¦_	| Flattened list of digits
1C	| Count 1s

```

# Answer
> 1 votes
# Actually, 9 bytes

```
uax#$'1ac

```

Try it online!

## Explanation

```
uax#      Push the inclusive range
    $     Turn it into a string
     '1ac Count the amount of ones

```

# Answer
> 1 votes
# F# (.NET Core), 65 bytes

```
fun x y->Seq.sumBy(fun a->a.ToString().Split("1").Length-1){x..y}

```

Try it online!

# Answer
> 1 votes
# shellutils, 26 bytes

A similar idea to the challenger's example

```
seq $1 $2|grep -o 1|wc -l

```

Explanation

`seq` prints all the numbers in the range given, increasing by `1` if not specified.

`grep -0 1` prints all `1` characters, one on each line

`wc -l` prints the number of lines

# Answer
> 1 votes
## x86-32 assembly (26 bytes)

```
    xor    edi, edi       ; 31 FF     Set edi = 0 (counter for result)
    lea    esi, [edi+10]  ; 8D 77 0A  Set esi = 10
notFinished:
    mov    eax, ecx       ; 89 C8     eax contains the number to be checked next
notZero:
    xor    edx, edx       ; 31 D2
    div    esi            ; F7 F6     Separate digit from current number
    cmp    dl, 1          ; 80 FA 01  Check if this digit was one
    jne    notOne         ; 75 01
    inc    edi            ; 47        When the digit was one, increase counter
notOne:
    test   eax, eax       ; 85 C0
    jnz    notZero        ; 75 F2     Loop until all digits of current number are checked
    cmp    ebx, ecx       ; 39 CB
    loopnz notFinished    ; E0 EC     Loop until end of range is reached
    ret                   ; C3

```

Online working example

Intel syntax is used here. The opcodes are given in the middle column between the source code and the comments. The parameters are transferred in registers:

* `ebx` contains range start
* `ecx` contains range end

The result is returned in the `edi` register.

**Credit:** Thanks to 640KB for pointing out that looping from high to low saves one byte here.

# Answer
> 1 votes
# Clojure, 73 bytes

```
(defn h[s e](count(filter #(= \1 %)(into[](apply str(range s(inc e)))))))

```

Try it online!

Ungolfed:

```
(defn how-many-ones [start end]
  (count (filter #(= \1 %) (into [] (apply str (range start (inc end)))))))

```

# Answer
> 1 votes
# Swift, 50 bytes

```
{($0...$1).flatMap{"\($0)".filter{$0=="1"}}.count}

```

Short explanation: Maps every number in the range to a string and filters every character which is equal to 1 and counts the resulting characters.

Try it online!

# Answer
> 1 votes
# Vyxal, `s`, 4 bytes

```
ṡƛ1O

```

Try it Online!

## Explained

```
ṡƛ1O;
ṡ       # Create an inclusive range between the two inputs
 ƛ      # For each item in that range:
  1O    #   Count the number of 1s
        # The 's' flag autosums t.o.s and implicitly prints.

```

# Answer
> 1 votes
# 05AB1E, 4 bytes

```
ŸJ1¢

```

Try it online! Takes two lines of input, the first one being `b` and the second being `a`.

```
   ¢  # total number of
  1   # ones
   ¢  # in
 J    # joined elements of
Ÿ     # [a, ..., b]

```

# Answer
> 1 votes
# Julia, 26 bytes

```
a->b->count("1",join(a:b))

```

expects `f(a)(b)`

Try it online!

# Answer
> 1 votes
# Excel, 75 bytes

```
=SUM(LEN(SEQUENCE((F5-E5),,E5))-LEN(SUBSTITUTE(SEQUENCE((F5-E5),,E5),1,"")))

```

Not very efficient, but works. Sequence generates a sequence of integers, and using the length/substitute calculation the number of ones is calculated.

# Answer
> 0 votes
# Thunno 2 `SS`, 3 bytes

```
Idḅ

```

Try it online!

## Thunno 2, 4 bytes

```
IJ1c

```

Try it online!

#### Explanation

```
Idḅ   # Implicit input    ->  1, 100
I     # Inclusive range   ->  [1..100]
 d    # Digits of each    ->  [[1],[2],...,[9,9],[1,0,0]]
  ḅ   # Check for == 1    ->  [[1],[0],...,[0,0],[1,0,0]]
      # Sum (flatten)     ->  [1,0,...0,0,1,0,0]
      # Sum the list      ->  21
      # Implicit output

```

```
IJ1c  # Implicit input    ->  1, 100
I     # Inclusive range   ->  [1..100]
 J    # Join into string  ->  "123...99100"
  1c  # Count 1s          ->  21
      # Implicit output

```

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


title: Prime counting function

text:
# Question
Title: Prime counting function
## Introduction

The Prime Counting Function, also known as the Pi function \\$\pi(x)\\$, returns the amount of primes less than or equal to x.

## Challenge

Your program will take an integer x which you can assume to be positive, and output a single integer equal to the amount of primes less than or equal to x. This is a challenge, so the winner will be the program with the fewest bytes.

You may use any language of your choosing provided that it existed before this challenge went up, but if the language has a built-in prime-counting function or a primality checking function (such as Mathematica), that function cannot be used in your code.

## Example Inputs

Input:
`1`
Output:
`0`

Input:
`2`
Output:
`1`

Input:
`5`
Output:
`3`

A000720 - OEIS

# Answer
# 05AB1E, 3 bytes

```
!fg

```

This assumes that factorization built-ins are allowed. Try it online!

### How it works

```
!    Compute the factorial of the input.
 f   Determine its unique prime factors.
  g  Get the length of the resulting list.

```
> 41 votes

# Answer
## Python 2, 45 bytes

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

```

Uses the Wilson's Theorem prime generator. The product `p` tracks `(k-1)!^2`, and `p%k` is 1 for primes and 0 for nonprimes.
> 12 votes

# Answer
# MATL, ~~11, 10, 8~~, 5 bytes

```
:pYFn

```

Try it online!

I wrote a version that had a really cool explanation of how MATL's matrices work:

`:YF!s1=1`

But it's no longer relevant. Check out the revision history if you want to see it.

New explanation:

```
:p      % Compute factorial(input)
  YF    % Get the exponenents of prime factorization
    n   % Get the length of the array

```

*Three bytes saved thanks to Dennis's genius solution*
> 6 votes

# Answer
# Jelly, ~~8~~ 5 bytes

*3 bytes saved thanks to @Dennis!*

```
RÆESL

```

Try it online!

Port of DJMcMayhem's MATL answer (former version) refined by Dennis.

```
R          Range of input argument
 ÆE        List of lists of exponents of prime-factor decomposition
   S       Vectorized sum. This right-pads inner lists with zeros
    L      Length of result

```
> 5 votes

# Answer
# Retina 0.8.2, ~~31~~ 22 bytes

Byte count assumes ISO 8859-1 encoding.

```
.+
$*
(?!(..+)\1+$).\B

```

**Try it online** \- Input much larger than 2800 either times out or runs out of memory.

### References:

Martin's range generator

Martin's prime checker
> 5 votes

# Answer
# Perl, 33 bytes

Includes +1 for `-p`

Give the input number on STDIN

`primecount.pl`

```
#!/usr/bin/perl -p
$_=1x$_;$_=s%(?!(11+)\1+$)%%eg-2

```

Gives the wrong result for `0` but that's OK, the op asked for support for positive integers only.
> 5 votes

# Answer
# MediaWiki templates with ParserFunctions, 220 + 19 = 239 bytes

```
{{#ifexpr:{{{2}}}+1={{{1}}}|0|{{#ifexpr:{{{3}}}={{{2}}}|{{P|{{{1}}}|{{#expr:{{{2}}}+1}}|2}}|{{#ifexpr:{{{2}}} mod {{{3}}}=0|{{#expr:1+{{P|{{{1}}}|{{#expr:{{{2}}}+1}}|2}}|{{P|{{{1}}}|{{{2}}}|{{#expr:{{{2}}}+1}}}}}}}}}}}}

```

To call the template:

```
{{{P|{{{n}}}|2|2}}}

```

Arranged in Lisp style:

```
{{#ifexpr:{{{2}}} + 1 = {{{1}}}|0|
    {{#ifexpr:{{{3}}} = {{{2}}} |
        {{P|{{{1}}}|{{#expr:{{{2}}} + 1}}|2}} |
            {{#ifexpr:{{{2}}} mod {{{3}}} = 0 |
                {{#expr:1 + {{P|{{{1}}}|{{#expr:{{{2}}} + 1}}|2}} |
                {{P|{{{1}}}|{{{2}}}|{{#expr:{{{2}}} + 1}}}}}}}}}}}}

```

Just a basic primality test from 2 to *n*. The numbers with three braces around them are the variables, where `{{{1}}}` is *n*, `{{{2}}}` is the number being tested, `{{{3}}}` is the factor to check.
> 5 votes

# Answer
## PowerShell v2+, 98 bytes

```
param($n)if($j='001'[$n]){}else{for($i=1;$i-lt$n){for(;'1'*++$i-match'^(?!(..+)\1+$)..'){$j++}}}$j

```

*Caution:* This is **slow** for large input.

Basically the unary-based lookup from Is this number a prime?, coupled with a `for` loop and a `$j++` counter. A little additional logic on the front to account for edge cases input `1` and `2`, due to how the fenceposting works in the `for` loops.
> 4 votes

# Answer
# Jelly, ~~13 11 10 9 8 7~~ 6 bytes

**Using no built-in prime functions whatsoever**
-1 byte thanks to @miles (use a table)
-1 byte thanks to @Dennis (convert from unary to count up the divisors)

```
ḍþḅ1ċ2

```

**TryItOnline**
Or see the first 100 terms of the series `n=[1,100]`, also at **TryItOnline**

How?

```
ḍþḅ1ċ2 - Main link: n
 þ     - table or outer product, n implicitly becomes [1,2,3,...n]
ḍ      - divides
  ḅ1   - Convert from unary: number of numbers in [1,2,3,...,n] that divide x
                             (numbers greater than x do not divide x)
    ċ2 - count 2s: count the numbers in [1,2,3,...,n] with exactly 2 divisors
                   (only primes have 2 divisors: 1 and themselves)

```
> 4 votes

# Answer
# JavaScript (ES6), ~~45~~ 43 bytes

```
f=(n,x=n)=>n>1&&(--x<2)+(n%x?f(n,x):f(n-1))

```

A modification of my ~~36~~ ~~35~~ 33-byte primality function (1 byte saved by @Neil, 2 by @Arnauld):

```
f=(n,x=n)=>n>1&--x<2||n%x&&f(n,x)

```

(I can't post this anywhere because Is this number a prime? only accepts full programs...)

### Test snippet

```
f=(n,x=n)=>n>1&&(--x<2)+(n%x?f(n,x):f(n-1))
```

```
<input type="number" oninput="console.log('f('+this.value+') is '+f(this.value))" value=2>
```
> 4 votes

# Answer
# Jelly, 3 bytes

```
!Æv

```

Try it online!

### How it works

```
!Æv  Main link. Argument: n

!    Compute the factorial of n.
 Æv  Count the number of distinct prime factors.

```
> 4 votes

# Answer
# 05AB1E, 5 bytes

Assumes that prime factorization builtins are allowed.

Code:

```
LÒ1ùg

```

Explanation:

```
L      # Get the range [1, ..., input]
 Ò     # Prime factorize each with duplicates
  1ù   # Keep the elements with length 1
    g  # Get the length of the resulting array

```

Uses the **CP-1252** encoding. Try it online!
> 3 votes

# Answer
# Jelly, 6 bytes

```
Ḷ!²%RS

```

This uses only basic arithmetic and Wilson's theorem. Try it online! or verify all test cases.

### How it works

```
Ḷ!²%RS  Main link. Argument: n

Ḷ       Unlength; yield [0, ..., n - 1].
 !      Factorial; yield [0!, ..., (n - 1)!].
  ²     Square; yield [0!², ..., (n - 1)!²].
    R   Range; yield [1, ..., n].
   %    Modulus; yield [0!² % 1, ..., (n - 1)!² % n].
        By a corollary to Wilson's theorem, (k - 1)!² % k yields 1 if k is prime
        and 0 if k is 1 or composite.
     S  Sum; add the resulting Booleans.

```
> 3 votes

# Answer
# C# 5.0 78 77

```
int F(int n){int z=n;if(n<2)return 0;for(;n%--z!=0;);return(2>z?1:0)+F(n-1);}

```

Ungolfed

```
int F(int n)
{
    var z = n;
    if (n < 2) return 0;
    for (; n % --z != 0;) ;
    return F(n - 1) + (2 > z ? 1 : 0);
}

```
> 3 votes

# Answer
# Regex (Perl / Java / PCRE), 32 bytes

```
((?=(\2?+x*?(?!(xx+)\3+$))xx)x)*

```

Try it online! \- Perl
Try it online! \- Java
Try it online! \- PCRE

Takes its input in unary, as a string of `x` characters whose length represents the number. Returns its output as the length of the match.

```
        # tail = N = input value; no anchor needed, as every value returns a match
# Count the number of primes <= N, from the largest to the smallest prime.
(       # J = 0
    (?=
        # \2 starts at zero, and on each subsequent iteration, contains the difference
        # N-P-(J-1) where P is the previously found prime, and J is the running total of
        # our prime count.
        (
            \2?+           # Start from the previous value of \2, atomically so that it
                           # can't be backtracked and started again from zero if the
                           # following fails to match. This will make tail = P-1, where
                           # P is the previously found prime.
            x*?            # Advance as little as necessary to make the following match,
                           # and add this to \2, while subtracting it from tail.
            (?!(xx+)\3+$)  # Assert tail is not composite; note that this needs to be
                           # inside group \2 for it to work in PCRE1 and older versions of
                           # PCRE2, which atomicize groups that have nested backreferences
        )
        xx                 # Assert tail is prime by eliminating the false positives 0, 1
    )
    x   # J += 1; tail -= 1
)*      # Iterate zero or more times, until there are no more smaller primes
# Return J as our match

```

# Regex (Python`regex` / Ruby), ~~41~~ 39 bytes

```
((?=(?=(\3?))(\2x*?(?!(xx+)\4+$))xx)x)*

```

Try it online! \- Python `import regex`
Try it online! \- Ruby

This is a port of the Perl/Java/PCRE regex to flavors that have no support for nested backreferences. Python's built-in `re` module does not even support forward backreferences, so for Python this requires `regex`.

```
        # tail = N = input value; no anchor needed, as every value returns a match
# Count the number of primes <= N, from the largest to the smallest prime.
(       # J = 0
    (?=
        # \2 starts at zero, and on each subsequent iteration, contains the difference
        # N-P-(J-1) where P is the previously found prime, and J is the running total of
        # our prime count.
        (?=(\3?))          # \2 = \3 (or 0 if \3 is unset), to make up for the lack of
                           #      nested backreferences
        (
            \2             # Start from the previous value of \3 (as copied into \2).
                           # This will make tail = P-1, where P is the previously found
                           # prime.
            x*?            # Advance as little as necessary to make the following match,
                           # and add this to \3, while subtracting it from tail.
            (?!(xx+)\4+$)  # Assert tail is not composite; note that this needs to be
                           # inside group \3 for it to work in PCRE1 and older versions of
                           # PCRE2, which atomicize groups that have nested backreferences
        )
        xx                 # Assert tail is prime by eliminating the false positives 0, 1
    )
    x   # J += 1; tail -= 1
)*      # Iterate zero or more times, until there are no more smaller primes
# Return J as our match

```

# Regex (.NET), 35 bytes

```
((?=((?>\2?)x*?(?!(xx+)\3+$))xx)x)*

```

Try it online!

This is a direct port of the Perl/Java/PCRE regex.

# Regex (.NET), 35 bytes

```
^(?=(x*?(?!(xx+)\2+$)x)*x)(?<-1>x)*

```

Try it online!

This uses the .NET feature of balanced groups to do the counting. It does not return a value for zero, but doing so only requires +1 byte (**36 bytes**):

```
^(?=(x*?(?!(xx+)\2+$)x)*x|)(?<-1>x)*

```

Try it online!

```
^                      # tail = N = input number
(?=
    (
        x*?            # Advance as little as necessary to make the following match
        (?!(xx+)\3+$)  # Assert tail is not composite
        x              # Eliminate the false primality positive of 0, and advance forward
                       # so that the next prime can be found (if we didn't do this, the
                       # regex engine would exit the loop due to a zero-width match)
    )*                 # Every time this loop matches an iteration, the capture group 1
                       # match is pushed onto the stack. This (balanced groups) is how we
                       # count the number of primes.
    x                  # Eliminate the false primality positive of 1
|                      # Allow us to return a value of 0 for N=0
)
(?<-1>x)*              # Pop all of the group 2 captures off the stack, doing head += 1
                       # for each one. This gives us our return value match.

```

---

I strongly suspect this function is impossible to implement in ECMAScript regex, even with the addition of `(?*)` or `(?<=)` / `(?<!)`. There doesn't seem to be room to multiplex the count and the current prime into a single tail variable, but I don't know if this can be proved.

Only one variable can be modified within a loop, such that must decrease by at least 1 on every step – and only \\$O(n)\\$ space is available; no variable may contain a value larger than \\$n\\$, and the language has no concept of arrays (although it is possible to take them as immutable input), only scalar variables (i.e. capture groups and the cursor position).

So it would seem that calculating this function would require \\$O({n^2\over log(n)})\\$ scratch space, to multiplex the iteration count and current prime into a single number. While multiple loops in a row would be able to get closer to \\$\pi(n)\\$ than a single loop, the number of such loops could only be a constant; it seems that it would need to be able to grow with \\$n\\$ to be able to actually asymptotically calculate \\$\pi(n)\\$. And a nested loop would still have to distill all the information gained by its innermost loop into a single number \\$\le n\\$.

But these things are just indications and vague evidence, not a proof. I have set a bounty regarding this open question.
> 3 votes

# Answer
## Pyke, ~~8~~ 6 bytes

```
SmPs}l

```

Try it here!

Thanks to Maltysen for new algorithm

```
SmP    -    map(factorise, input)
   s   -   sum(^)
    }  -  uniquify(^)
     l - len(^)

```
> 2 votes

# Answer
# Pyth - ~~7~~ 6 bytes

Since others are using prime factorization functions...

```
l{sPMS

```

Test Suite.
> 2 votes

# Answer
# Bash + coreutils, 30

```
seq $1|factor|egrep -c :.\\S+$

```

Ideone.

---

# Bash + coreutils + BSD-games package, 22

```
primes 1 $[$1+1]|wc -l

```

This shorter answer requires that you have the bsdgames package installed: `sudo apt install bsdgames`.
> 2 votes

# Answer
# C#, 157 bytes

```
n=>{int c=0,i=1,j;bool f;for(;i<=n;i++){if(i==1);else if(i<=3)c++;else if(i%2==0|i%3==0);else{j=5;f=1>0;while(j*j<=i)if(i%j++==0)f=1<0;c+=f?1:0;}}return c;};

```

Full program with test cases:

```
using System;

class a
{
    static void Main()
    {
        Func<int, int> s = n =>
            {
                int c = 0, i = 1, j;
                bool f;
                for (; i <= n; i++)
                {
                    if (i == 1) ;
                    else if (i <= 3) c++;
                    else if (i % 2 == 0 | i % 3 == 0) ;
                    else
                    {
                        j = 5;
                        f = 1 > 0;
                        while (j * j <= i)
                            if (i % j++ == 0)
                                f = 1 < 0;
                        c += f ? 1 : 0;
                    }
                }
                return c;
            };

        Console.WriteLine("1 -> 0 : " + (s(1) == 0 ? "OK" : "FAIL"));
        Console.WriteLine("2 -> 1 : " + (s(2) == 1 ? "OK" : "FAIL"));
        Console.WriteLine("5 -> 3 : " + (s(5) == 3 ? "OK" : "FAIL"));
        Console.WriteLine("10 -> 4 : " + (s(10) == 4 ? "OK" : "FAIL"));
        Console.WriteLine("100 -> 25 : " + (s(100) == 25 ? "OK" : "FAIL"));
        Console.WriteLine("1,000 -> 168 : " + (s(1000) == 168 ? "OK" : "FAIL"));
        Console.WriteLine("10,000 -> 1,229 : " + (s(10000) == 1229 ? "OK" : "FAIL"));
        Console.WriteLine("100,000 -> 9,592 : " + (s(100000) == 9592 ? "OK" : "FAIL"));
        Console.WriteLine("1,000,000 -> 78,498 : " + (s(1000000) == 78498 ? "OK" : "FAIL"));
    }
}

```

Starts to take awhile once you go above 1 million.
> 2 votes

# Answer
# Jelly, 3 bytes

```
ÆRL

```

Jelly has a built-in prime counting function, `ÆC` and a prime checking function, `ÆP`, this instead uses a built-in prime generating function, `ÆR` and takes the length `L`.

I guess this is about as borderline as using prime factorisation built-ins, which would also take 3 bytes with `!Æv` (`!` factorial, `Æv` count prime factors)
> 2 votes

# Answer
# Matlab, 60 bytes

Continuing my attachment to one-line Matlab functions. Without using a factorisation built-in:

```
f=@(x) nnz(arrayfun(@(x) x-2==nnz(mod(x,[1:1:x])),[1:1:x]));

```

Given that a prime `y` has only two factors in `[1,y]`: we count the numbers in the range `[1,x]` which have only two factors.

Using factorisation allows for significant shortening (down to 46 bytes).

```
g=@(x) size(unique(factor(factorial(x))),2);

```

Conclusion: Need to look into them golfing languages :D
> 2 votes

# Answer
# MATL, 9 bytes

This avoids prime-factor decomposition. Its complexity is O(*n*²).

```
:t!\~s2=s

```

Try it online!

```
:     % Range [1 2 ... n] (row vector)
t!    % Duplicate and transpose into a column vector
\     % Modulo with broadcast. Gives matrix in which entry (i,j) is i modulo j, with
      % i, j in [1 2 ... n]. A value 0 in entry (i,j) means i is divisible by j
~     % Negate. Now 1 means i is divisible by j
s     % Sum of each column. Gives row vector with the number of divisors of each j
2=    % Compare each entry with 2. A true result corresponds to a prime
s     % Sum

```
> 2 votes

# Answer
# PHP, ~~96~~ 92 bytes

```
for($j=$argv[1]-1;$j>0;$j--){$p=1;for($i=2;$i<$j;$i++)if(is_int($j/$i))$p=0;$t+=$p;}echo $t;

```

Saved 4 bytes thanks to Roman Gräf

Test online

Ungolfed testing code:

```
$argv[1] = 5;

for($j=$argv[1]-1;$j>0;$j--) {
    $p=1;
    for($i=2;$i<$j;$i++) {
        if(is_int($j/$i)) {
            $p=0;
        }
    }
    $t+=$p;
}
echo $t;

```

Test online
> 2 votes

# Answer
# Actually, 10 bytes

This was the shortest solution I found that didn't run into interpreter bugs on TIO. Golfing suggestions welcome. Try it online!

```
;╗r`P╜>`░l

```

**Ungolfing**

```
         Implicit input n.
;╗       Duplicate n and save a copy of n to register 0.
r        Push range [0..(n-1)].
`...`░   Push values of the range where the following function returns a truthy value.
  P        Push the a-th prime
  ╜        Push n from register 0.
  >        Check if n > the a-th prime.
l        Push len(the_resulting_list).
         Implicit return.

```
> 2 votes

# Answer
# Java 8, ~~95~~ 84 bytes

```
z->{int c=0,n=2,i,x;for(;n<=z;c+=x>1?1:0)for(x=n++,i=2;i<x;x=x%i++<1?0:x);return c;}

```

**Explanation:**

Try it online.

```
z->{                // Method with integer parameter and integer return-type
  int c=0,          //  Start the counter at 0
      n=2,          //  Starting prime is 2
      i,x;          //  Two other temp integers
  for(;n<=z;        //  Loop (1) as long as `n` is smaller than or equal to the input `z`
       c+=x>1?1:0)  //    and increase the counter if we've came across a prime
                    //    (if `x` is larger than 0, it means the current `n` is a prime)
     for(x=n++,i=2;i<x;x=x%i++<1?0:x);
                    //   Determine if the next integer in line is a prime by setting `x`
                    //   (and increase `n` by 1 afterwards)
                    //  End of loop (1) (implicit / single-line body)
  return c;         //  Return the resulting counter
}                   // End of method

```
> 2 votes

# Answer
# APL (Dyalog Unicode), 13 bytesSBCS

```
2+.=0+.=⍳∘.|⍳

```

Try it online!

**ɩ**ndices 1…N
⧽ `∘.|` remainder-table (using those two as axes)
**ɩ**ndices 1…N

`0+.=` the sum of the elements equal to zero (i.e. how many dividers does each have)

`2+.=` the sum of the elements equal to two (i.e. how many primes are there)
> 2 votes

# Answer
# APL (Dyalog Unicode), 12 bytes

```
(≢⊢~∘.×⍨)1↓⍳
 ≢ ⍝ tally
  ⊢~ ⍝ index values not in matrix of composite numbers
    ∘.×⍨ ⍝ outer product of positive integers with themselves
        1↓⍳ ⍝ range from 1–n less the first element

```

h/t @adám

Try it online!
> 2 votes

# Answer
# C (clang), 49 bytes

```
p(n,i){for(i=n;--i&&n%i;);return--n?p(n)+!--i:0;}

```

Assumes `n` is positive.

Try it online!
> 2 votes

# Answer
# Thunno, \\$ 4 \log\_{256}(96) \approx \\$ 3.29 bytes

```
FAFL

```

Attempt This Online!

Port of Dennis's 05AB1E answer.

#### Explanation

```
F       # Push the factorial of the input
 AF     # Get the unique prime factors
   L    # Push the length of the list

```
> 2 votes

# Answer
## JavaScript (ES6), ~~50+2~~ ~~46+2~~ 43 bytes

Saved ~~3~~ 5 bytes thanks to Neil:

```
f=n=>n&&eval(`for(z=n;n%--z;);1==z`)+f(n-1)

```

`eval` can access the `n` parameter.
The `eval(...)` checks if `n` is prime.

---

**Previous solutions:**
Byte count should be +2 because I forgot to name the function `f=` (needed for recursion)

46+2 bytes (Saved 3 bytes thanks to ETHproductions):

```
n=>n&&eval(`for(z=n=${n};n%--z;);1==z`)+f(n-1)

```

50+2 bytes:

```
n=>n&&eval(`for(z=${n};${n}%--z&&z;);1==z`)+f(n-1)

```
> 1 votes

# Answer
# Java 7,102 bytes

**Brute force**

```
int f(int n){int i=2,j=2,c=1,t=0;for(;i<=n;j=2,c+=t==1?1:0,i++)for(;j<i;t=i%j++==0?j=i+1:1);return c;}

```

# Ungolfed

```
int f(int n){
int i=2,j=2,c=1,t=0;
for(;i<=n;j=2,c+=t==1?1:0,i++)
    for(;j<i;)
        t=i%j++==0?j=i+1:1;
    return c;
 }

```
> 1 votes

# Answer
# q 35 bytes

```
{sum 1=sum'[0=2_' a mod\: a:til x]}

```
> 1 votes

# Answer
# Actually, 10 bytes

If my first Actually answer is disallowed for using a prime-generating function, here is a backup answer using Wilson's theorem. Golfing suggestions welcome. Try it online!

```
R`;D!²%`MΣ

```

**Try it online**

```
         Implicit input n.
R        Push range [1..n]
`...`M   Map the following function over the range. Variable k.
  ;        Duplicate k.
  D        Decrement one of the copies of k.
  !²       Push ((k-1)!)².
  %        Push ((k-1)!)² % k. This returns 1 if k is prime, else 0.
Σ        Sums the result of the map, adding all the 1s that represent primes,
          giving the total number of primes less than n.
         Implicit return.

```
> 1 votes

# Answer
## Racket 60 bytes

```
(require math)(λ(n)(length(filter prime?(range 1(+ 1 n)))))

```

Testing:

```
(require math)
(define f
    (λ(n) (length (filter prime? (range 1 (+ 1 n)))))
)

(f 1)
(f 2)
(f 3)
(f 5)

```

Output:

```
0
1
2
3

```
> 1 votes

# Answer
# PARI/GP, 15 bytes

```
n->#factor(n!)~

```

Take the factorial and count its unique prime factors.
> 1 votes

# Answer
# Actually, 3 bytes

This uses a prime factorization function, which may or may not be allowed after the OP clarifies. Golfing suggestions welcome. Try it online!

```
!yl

```

**Ungolfing**

```
     Implicit input n.
!    Push n factorial.
 y   Push a list of all of the positive prime factors of n! (every prime < n)
  l  Take the length of that list of primes.
     Implicit return.

```
> 1 votes

# Answer
# Pyt, 3 bytes

```
řṗƩ

```

Explanation:

```
ř         Push [1,2,...,input]
 ṗ        Elementwise isPrime(k)
  Ʃ       Sum of array (autoconverts booleans to 0/1)

```

Try it online!
> 1 votes

# Answer
# Perl 6, 31 bytes

```
{+grep {$_%%none 2..^$_},2..$_}

```

Try it online!
> 1 votes

# Answer
# (pure) BASH, 138 bytes

Look, Mom!
No preloaded prime tables, no prime related builtins, not even a division or plultimication!

```
a=2
l=0
while((a<=$1));do if((b[a]))
then((c=b[a]));else((c=a,l++));fi;((d=a+c))
while((b[d]));do((d+=c));done
((b[d]=c,a++));done;echo $l

```

Eating the pudding:

```
$ for i in 1 2 3 11033 ; do bash fsoe-primecounter-in-bash $i ; done
0
1
2
1337

```

Ok, probably looping while looking at candidates modulo all possible divisors would have been shorter in "pure BASH" too but we've seen those loops at least 1001 times now.

This solution builds its own prime table on the fly and so is bearably fast even in "pure BASH".
> 1 votes

# Answer
## Python 3, 40 bytes

```
f=lambda n:1if n<1else(2**n%n==2)+f(n-1)

```

An odd integer k is prime if an only if 2\**(k-1) is congruent to 1 mod k. Thus, we just check for this condition and add 1 for the case of k=2.
> 1 votes

# Answer
# APL NARS, 150 bytes

```
∇r←g n;h;i;k
i←0⋄h←1+⍳n-1⋄→B
A:k←i⊃h⋄h←k∪(0≠k∣h)/h
B:→A×⍳(⍴h)≥i+←1
r←⍴h
∇

```

this would be the "Crivello di Eratostene" or something as that.

If h=2..n

In the first iteration of the loop eliminate each multiple of 2 in h except 2

in the second iteration of the loop eliminate each multiple of 3 in h except 3

...

return the number of final element of h.(in h primes return ⍴h)

```
  g¨1 2 5
0  1  3
  g 20000
2262

```

As note negative for the question: There would be a range limit for the arg of the function; something as 1..20000 and each answer would indicate the range the argument has to be for to be safe to pass to the function (without one seg fault in the code, without one memory insufficient for the program, without one incorrect value return as result )
> 1 votes

# Answer
# Pyth, 6 bytes

```
l{P.!Q

```

Explanation follows:

```
   .!Q Factorial of input
  P    List primes of factorial with multiplicity
 {     Remove duplicates formed by said multiplicity
l      Length of deduplicated list

```
> 1 votes

# Answer
# Add++, 17 bytes

```
L,RB*f0b]@bLA1=!*

```

Try it online!
> 1 votes

# Answer
# Kotlin, 85 bytes

```
{n:Int->var r=0
for(i in 2..n){var t=1
for(p in 2..i/2)if(i%p==0){t--
break}
r+=t}
r}

```

Try it online!

Try lambda for first time as saved 16 bytes.

# Kotlin, 101 bytes

```
fun c(n:Int):Int{var r=0
for(i in 2..n){var t=1
for(p in 2..i/2)if(i%p==0){t--
break}
r+=t}
return r}

```

Try it online!
> 1 votes

# Answer
# Haskell, ~~46~~ 42 bytes

```
p n=sum[mod(product[1..i-1]^2)i|i<-[1..n]]

```

Try it online!
> 1 votes

# Answer
# Python 3, ~~197~~ 165 bytes

Removed the need for the import math by checking every divisor of i besides i itself, though mathematically only checking up to the square root is required.

```
def c(x):
    p=0
    for i in range(2,x+1):
        P=1
        for d in range(1,i):
            if i%d==0 and d!=1:
                P=0
        p+=1*P
    return p

```

Original:

```
import math
def c(x):
    p=0
    for i in range(2,x+1):
        P=1
        for d in range(1,round(math.sqrt(i))+1):
            if i%d==0 and d!=1:
                P=0
        p+=1*P
    return p

```
> 1 votes

# Answer
# Vyxal `l`, 2 bytes

```
¡Ǐ

```

Try it Online! \- test cases only

This is the same as the 3 byte answer below except the length is taken by the `l` flag rather than an `L` element.

# Vyxal, 3 bytes

```
¡ǏL

```

Try it Online!

```
¡  # Factorial
Ǐ  # Prime factorization - list of distinct prime factors
L  # Length of that list

```

Direct port of Dennis's 05AB1E solution, which is the accepted answer, so one would infer that it meets the challenge's specifications.

The element  could be considered a "prime-counting function", even though it counts the distinct prime factors of the input, not the primes less than or equal to the input. The solution using that built-in is **2 bytes**:

```
¡†

```

Try it Online!

```
¡  # Factorial
†  # Number of distinct prime factors

```

# Vyxal, 9 bytes

```
ɾ⟑‹¡²$%;∑

```

Try it Online!

With no factorization built-ins, instead using Wilson's theorem:

```
ɾ  # Inclusive One Range (from 1 to input)
⟑  # Apply lambda to each individual list item:
‹  # Subtract 1
¡  # Factorial
²  # Square
$  # Swap
%  # Modulo - this will be (n-1)!² % n
;  # Close lambda
∑  # Sum

```

With the `r` flag this is **8 bytes**: Try it Online!
With the `rs` flags this is **6 bytes**: Try it Online!
> 1 votes

# Answer
# Python 2, 55 bytes

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

```

Try it online!

A programification of the below. The Python 3 equivalent is 62 bytes.

Note that although xnor's recursive answer outgolfs this at **45 bytes**, it cannot handle an input of `999` or greater, due to Python's recursion limit: Try it online! \- this limit can be increased, though: Try it online!

This 55 byte solution can go well beyond that. For example, all inputs up to `3000`: Try it online!

# Python 3.8+, ~~57~~ 54 bytes

```
lambda n,p=1:sum([(p:=p*i*i)%-~i for i in range(1,n)])

```

Try it online! / Attempt This Online!

A lambdafication of the below, taking advantage of the `:=` operator.

Although xnor's recursive answer outgolfs this at **46 bytes** when ported to Python 3, it still can't handle an input of `999` or greater: Try it online! \- this limit can be increased: Attempt This Online!

# Python, 59 bytes

```
def P(n):
 s=p=i=1
 while i<n:p*=i*i;i+=1;s+=p%i
 return~-s

```

Try it online! \- Python 2
Try it online! \- Python 3

Based on miles's answer to "Is it a super-prime?".

This exploits Wilson's theorem and Python's arbitrary precision integers to count primes. At each iteration of the loop, with \\$i\in\[2,n\]\\$, it calculates \\${(i-1)^2}!\pmod i\\$. This \\$\equiv 1\\$ when \\$i\\$ is prime and \\$\equiv 0\\$ otherwise. The squaring is done to compensate for the fact that \\$4\\$ is the only exception, with \\$(4-1)!\equiv 2\pmod 4\\$, but \\$(4-1)^2!\equiv 0\pmod 4\\$. Note that squaring also changes the modulus from \\$-1\\$ to \\$1\\$ for prime \\$i\\$.

If not for the exception at `i=4`, we could have done

```
while i<n:p*=i;i+=1;s+=-p%i

```

For 1 byte less, because Python returns a positive result when taking a negative number modulo a positive number.
> 1 votes

# Answer
# Stax, 4 bytes

```
Ü:÷/

```

Run and debug it

Same approach as many other answers. This is a packed stax program which unpacks to the following 5 bytes:

```
|F:F%

```

Run and debug it

# Explanation

```
|F    # factorial of input
  :F  # distinct prime factors
    % # length

```
> 1 votes

# Answer
# Japt, 6 bytes

```
Êk â Ê

```

Try it

```
Êk â Ê     :Implicit input of integer
Ê          :Factorial
 k         :Prime factors
   â       :Deduplicate
     Ê     :Length

```
> 1 votes

# Answer
# Thunno 2 `L`, 2 bytes

Try it online!

Port of Dennis's 05AB1E answer.

#### Explanation

```
wƑ  # Implicit input
w   # Factorial of input
 Ƒ  # Unique prime factors
    # Implicit output of length

```
> 0 votes

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