title: Halve the falses

text:
# Question
Title: Halve the falses
# Task

Given a **non-empty** array of `0` and `1`, halve the lengths of the runs of `0`.

# Input

An array of `0` and `1`. Acceptable format:

* Real array in your language
* Linefeed-separated string of `0` and `1`
* Contiguous string of `0` and `1`
* Any other reasonable format

For example, the following three inputs are all acceptable:

* `[1, 0, 0, 1]`
* `"1\n0\n0\n1"` (where `\n` is a linefeed U+000A)
* `"1001"`

You may assume that the runs of `0` will have **even length**.

# Output

An array of `0` and `1`, in the acceptable formats above.

# Testcases

```
input ↦ output
[1,0,0,1,0,0,1] ↦ [1,0,1,0,1]
[1,1,0,0,1,1,0,0,1] ↦ [1,1,0,1,1,0,1]
[1,1,0,0,1,1,1,0,0,1,1] ↦ [1,1,0,1,1,1,0,1,1]
[1,1,1] ↦ [1,1,1]
[0,0,1] ↦ [0,1]
[0,0] ↦ [0]
[1,1,1,0,0,0,0,1,1,1,1,0,0,1,0,0,1,1,0,0,1,1,1,1,0,0,1,0,0] ↦ [1,1,1,0,0,1,1,1,1,0,1,0,1,1,0,1,1,1,1,0,1,0]

```

# Scoring

This is . Shortest answer in bytes wins.

Standard loopholes apply.

# Answer
## Retina, 4 bytes

```
00
0

```

Try it online!
> 32 votes

# Answer
# 05AB1E, 5 bytes

```
00¤.:

```

Try it online!

**Explanation**

```
00     # push 00
  ¤    # tail, pushes 0
   .:  # replace

```
> 14 votes

# Answer
# Haskell, 33 bytes

```
f(0:0:r)=0:f r
f(x:r)=x:f r
f e=e

```

Try it online! Usage: `f[1,1,0,0,1,1,0,0,1]`. Iterates over the list and replaces two consecutive zeros by one zero.
> 9 votes

# Answer
# C (gcc), 35 bytes

```
f(char*s){while(*s)putchar(*s),*s++-48?:s++;}

```

48 is the ascii code of '0'

better version 43 bytes as suggested by Neil

```
f(char*s){while(*s)putchar(*s),s+=2-*s%2;}

```

another one 40 byte this time (again as suggested by Neil & VisualMelon) :)

```
f(char*s){for(;*s;s+=50-*s)putchar(*s);}

```

and then 35 bytes thanks to Khaled.K

```
f(char*s){*s&&f(s+50-putchar(*s));}

```

Try it online!
> 8 votes

# Answer
# sed, 8 bytes

```
s/00/0/g

```

Try it online!
> 7 votes

# Answer
# Octave, 22 bytes

```
@(s)strrep(s,'00','0')

```

**Verify all test cases here.**

This is an anonymous function taking a string on the format `'1001000011'` as input, and replaces two consecutive zeros with a single zero.
> 6 votes

# Answer
# Haskell, 28 bytes

```
f(h:t)=h:f(drop(1-h)t)
f e=e

```

Try it online!

Recursively takes the first element, dropping the second one if the first one is zero, until the list of empty. If the first entry is `h`, then the first `1-h` are dropped from the remainder.
> 6 votes

# Answer
# Java, 50 bytes

```
String f(String s){return s.replaceAll("00","0");}

```

**Try Online**
> 6 votes

# Answer
# Japt, ~~7 6~~ 5 bytes

```
d'0²0

```

Try it online!

Simply replaces each run of two zeroes in the input by one zero. Uses string input (i.e. `"1001001"`).
> 6 votes

# Answer
# Husk, 4 bytes

```
fG=¹

```

Try it online!

**How?**
The Husk `scanl` command (`G`) applies a function to each element of a list and the result-so-far. The initial result-so-far is set to the first element.

In this case, used with the `eq` (`=`) function, it checks whether each element is equal to the result-so-far. For runs of `1`, this will always output `1` (truthy). Now, the first of any run of `0`s will be `0` (falsy), of course; then, the next result will be `1` (since `0` is equal to the result-so-far), and then `0`, and so on, alternating `0`s at odd positions in the run and `1`s at even positions, until the end of the run. Since there are always an even number of `0`s in each run, then last result-so-far must be `1`: so, when we enter the next run of `1`s, the first result will be `1` (truthy) again, and so on...

So: runs of `0`s get alternating `0` and `1`, and runs of `1`s always get `1`, and we just need to `filter` (`f`) the input list (`¹`) by this.
> 6 votes

# Answer
## Alice, 13 bytes

```
/oe00/
@iS0e\

```

Try it online!

### Explanation

```
/.../
@...\

```

This is a simple template for linear programs which operate entirely in Ordinal mode. The initial `/` reflects the IP to move south east and then it bounces diagonally up and down through the code until the mirrors at the end. Those simply offset the position by one so that on the way back the IP traverses the remaining cells. Reading the code in this zigzag fashion it becomes:

```
ie00e0So@

```

This is a simple string substitution:

```
i   Read all input.
e   Push an empty string.
00  Append two zeros to create the string "00".
e   Push an empty string.
0   Append a zero to create the string "0".
S   Substitute all occurrences of "00" in the input with "0".
o   Output the result.
@   Terminate the program.

```

There are a few other ways to push the two strings, e.g. `'00'0` or `e000t`, but I haven't found anything that beats 5 bytes there (and I'd have to shave off two bytes to be able to shorten the program).
> 5 votes

# Answer
# Jelly, 8 bytes

```
ṣ1j1,1m2

```

Try it online!

Possibly other answers in languages without a `.replace()` or similar could use this trick.

**Explanation**

```
ṣ1j1,1m2 - (duplicates the 1s, then halves all lengths)
ṣ1       - split by the element 1
  j1,1   - join the elements with the two-element list 1,1
      m2 - get every second element

```
> 5 votes

# Answer
# Perl 5, 7+1(-p flag)=8 bytes

```
<>if/0/

```

Takes input as newline separated numbers. Skips the next line if it sees a zero.
> 5 votes

# Answer
# sed, ~~8~~ 6 bytes

```
n;/0/d

```

Try it online!

Takes a linefeed-separated string of `0` and `1`.

`n` skips a line, and `/0/d` deletes a line if it has a zero in it. This has the net effect of deleting every `0` on an even-numbered line. Since any even-length contiguous list of `0` has the same number of even-numbered and odd-numbered lines, this has the effect of halving the length of every run of `0`.
> 5 votes

# Answer
# , 4 bytes

```
òf0x

```

Try it online!

```
ò    ' Recursively (until we error)
 f0  ' Go to the next zero (errors when there are no zeros left)
   x ' Delete it

```
> 5 votes

# Answer
# Jelly, 4 bytes

```
¹‘ƭƇ

```

Try it online!

## Explanation

```
¹‘ƭƇ   Main monadic link
   Ƈ   Filter by
  ƭ      Every time this is called, switch between
¹          doing nothing and
 ‘         adding 1

```
> 5 votes

# Answer
# Prolog (SWI), 42 bytes

```
[0,0|T]*[0|R]:-T*R.
[H|T]*[H|R]:-T*R.
H*H.

```

Try it online!
> 4 votes

# Answer
# PHP, 26

```
<?=strtr($argn,["00"=>0]);

```

simply replace all `00` by `0`.
> 4 votes

# Answer
# MATL, 5 bytes

```
FFOZt

```

**Try it online!**

### Explanation

This is similar to Stewie Griffin's Octave answer:

```
FF     % Push [0 0]
O      % Push 0
Zt     % Implicitly take input. Replace [0 0] by 0. Implicitly display

```

---

# 8 bytes

```
vy~f2L)(

```

This avoids the string/array replacement builtin.

**Try it online!**

### Explanation

Consider input `[1,0,0,1,0,0,1]` as an example:

```
v      % Concatenate stack (which is empty): pushes []
       % STACK: []
y      % Implicit input. Duplicate from below
       % STACK: [1,0,0,1,0,0,1], [], [1,0,0,1,0,0,1]
~f     % Negate, find: gives indices of zeros
       % STACK: [1,0,0,1,0,0,1], [], [2,3,5,6]
2L     % Push [2,2,1i]. As an index, this is interpreted as 2:2:end
       % STACK: [1,0,0,1,0,0,1], [], [2,3,5,6], [2,2,1i]
)      % Reference indexing. This selects the even-indexed entries
       % STACK: [1,0,0,1,0,0,1], [], [3,6]
(      % Assignment indexing. This deletes the specified entries
       % (assigns them the empty array). Implicitly display
       % STACK: [1,0,1,0,1]

```
> 4 votes

# Answer
# Lua, 33 bytes

```
print((io.read():gsub("00","0")))

```

Takes a string via input and condenses double zeros. Easy.
> 4 votes

# Answer
# Alice, ~~12~~ 10 bytes

*2 bytes saved thanks to Martin Ender*

```
i.h%.7%$io

```

Try it online!

### Explanation

This is a 1-D code operating in cardinal mode, so it's easy to follow its flow:

```
i                   Read a byte from input (pushes -1 on EOF)
 .h                 Duplicate it and add 1 to the copy
   %                Compute n%(n+1). This will exit with an error on n==-1
                    and return n for any non-negative n.
    .7%             Duplicate the input again and compute its value modulo 7
                    This returns 6 for '0' (unicode value 48) and 0 for '1'
                    (unicode value 49)
       $i           If this last result was not 0, input another number.
                    This ignores every other '0' in the input
                    and moves to the following number (another '0')
         o          Output the last byte read

                    At the end, wrap back to the beginning of the line

```
> 4 votes

# Answer
# JavaScript (ES6), ~~26~~ 21 bytes

Takes the input as a string and returns a string.

```
s=>s.replace(/00/g,0)

```

---

## Try It

```
f=
s=>s.replace(/00/g,0)
i.addEventListener("input",_=>o.innerText=f(i.value))
console.log(f("1001001")) // "10101"
console.log(f("110011001")) // "1101101"
console.log(f("11001110011")) // "110111011"
console.log(f("111")) // "111"
console.log(f("001")) // "01"
console.log(f("00")) // "0"
console.log(f("11100001111001001100111100100")) // "1110011110101101111010"
```

```
<input id=i><pre id=o>
```
> 3 votes

# Answer
# Java, ~~131~~ 123 bytes

```
int[]f(int[]a){int c=0,i=0,l=a.length;for(int x:a)c+=1-x;int[]r=new int[l-c/2];for(c=0;c<l;c+=2-a[c])r[i++]=a[c];return r;}

```

Try it online!
> 3 votes

# Answer
# Mathematica, 24 bytes

```
StringReplace["00"->"0"]

```

A function that expects a string of `"0"`s and `"1"`s and returns a similar string. Self-explanatory syntax. Mathematica has lots of transformation builtins; the key is to use one that transforms every relevant subexpression (unlike `/.`) but only passes through the expression once (unlike `//.`).
> 3 votes

# Answer
# Pip, 5 bytes

```
aR00i

```

Takes a string of 0s and 1s. Try it online!

### Explanation

Beating Jelly? Inconceivable!

```
a      Take the first command-line argument
 R     and replace
  00   00 (an integer literal, so it doesn't need quotes)
    i  with i (variable preinitialized to 0)
       Autoprint

```
> 3 votes

# Answer
# , 21 bytes

```
function(n)n[n+1:0>0]

```

Try it online!
> 3 votes

# Answer
# Vyxal, 4 bytes

```
ɖ=Tİ

```

Try it Online! Port of Dominic van Essen's Husk answer. See that for a more detailed explanation of how this works.

```
ɖ    # Scan by
 =   # Equal to the current result?
     # For runs of 1s, this is 1,
     # For runs of 0s this alternates between 1 and 0
  Tİ # Keep only items wihtt a 1 in the previous list

```
> 3 votes

# Answer
# Brachylog, 10 bytes

```
ḅ{cẹ|ḍh}ᵐc

```

Try it online!

Not sure this is optimal yet…

### Explanation

This exploits the bug that `c` on a list of integers that has leading zeroes will fail.

```
ḅ               Blocks; group consecutive equal elements together
 {     }ᵐ       Map on each block:
  c               It is possible to concatenate the block into an int (i.e. it contains 1s)
   ẹ              Split it again into a list of 1s
    |             Else
     ḍh           Dichotomize and take the head
         c      Concatenate the blocks into a single list

```
> 2 votes

# Answer
# Python (list I/O), 36 bytes

```
f=lambda l:l and l[:1]+f(l[2-l[0]:])

```

Try it online!

Recursively takes the first element, then removes the remaining one if the first one was zero.

---

**38 bytes:**

```
lambda l:eval(`l`.replace('0, 0','0'))

```

Try it online This takes a Python list and outputs a Python list by doing replacement on its string representation. String I/O would allow a more direct and shorter solution, such as

```
lambda s:s.replace('00','0')

```

for `'1001'` format.
> 2 votes

# Answer
# ///, 11 bytes

```
/00/a//a/0/<input goes here>

```

Try it online!

Fun fact: `/00/0/<input>` won't work, because it reduces `0000` to `0`. Hence the `a`-substitute.
> 2 votes

# Answer
## Batch, 24 bytes

```
@set/ps=
@echo %s:00=0%

```

Takes input on STDIN. Somewhat competitive for once.
> 2 votes

# Answer
# APL (Dyalog), 9 bytes

```
'00'⎕R'0'

```

Try it online!
> 2 votes

# Answer
# Common Lisp, SBCL, ~~48~~ 32 bytes

*-16 bytes thanks to Julian Wolf*

```
(format t"~{~[0~*~;1~]~}"(read))

```

input:

```
(1 0 0 0 0 1 1 1 0 0)

```

output:

```
1001110

```

### Explanation

We read input list. List is used in `format` function. We loop through it outputting `1` if element is `1` and outputting `0` and skipping next element of list for `0`.
> 2 votes

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

```
->a{a.each_index{|i|a[i]>0||a[i..i]=[]}}

```
> 2 votes

# Answer
# Jelly, 10 bytes

```
Œg¹m2$S?€F

```

Try it online!

**Explanation**

```
Œg¹m2$S?€F
Œg          - Group runs of equal elements
        €   - To each run...
      S?    - If sum is truthy,
  ¹         -   return the run as it is
   m2$      - Else return every second element of the run.

```
> 2 votes

# Answer
# BitCycle, ~~18~~ ~~17~~ 15 bytes

*Saved 2 bytes via a clever rearrangement by Jo King*

```
?ABv
  +\!
 ^\<

```

Try it online!

### Algorithm

Take two bits of the input at a time. Output the first one. Discard the second one if it is 0 and output it if it is 1.

Because we are guaranteed that all runs of 0s have even length, this approach will always discard half of the 0s from each run:

```
00 -> 0x
10 01 -> 1x 01
10 0  -> 1x 0

```

### Implementation

The input bitstring comes in at the source `?` and is directed into the `A` collector, which in turn dumps its output into the `B` collector. Each time the `B` collector opens, the bits are directed through the two splitters `\`, which split off the first and second bits. The first bit goes east, straight into the sink `!` to be output. The second bit passes through the now-deactivated first splitter, hits the second splitter, and goes north into the `+`, which sends a 0 bit left (west) and off the playfield, but sends a 1 bit right (east) into the sink `!` to be output.

Meanwhile, the rest of the bits pass through both splitters and back into the `A` collector. Once they are all there, `A` opens and the cycle starts over. This loop continues until all bits are disposed of.
> 2 votes

# Answer
# Husk, ~~8~~ 7 bytes

```
ṁ?IĊ2←g

```

Try it online!

might be shorter with strings.

-1 byte from Zgarb.

## Explanation

```
ṁ?Io←½←g
       g group equal runs of elements
ṁ        map each group to function, and concatenate
 ?    ←  if first element is truthy
  I      leave as is
   o←½   else remove the second half

```
> 2 votes

# Answer
# Factor, 18 bytes

```
[ "00""0"replace ]

```

Try it online!
> 2 votes

# Answer
# , 29 bytes

```
function(n)n[n|cumsum(!n)%%2]

```

Try it online!

Input as list of `0` and `1` or T/F
> 2 votes

# Answer
# Excel, ~~24~~ 22 bytes

Saved 2 bytes thanks to Taylor Raine seeing what should have been obvious.

```
=SUBSTITUTE(A1,"00",0)

```

Inputs is a contiguous string of `0` and `1` in cell `A1`. Output is wherever the formula is.

Straightforward use of a built-in.

---

If the output has to be an array even though the input isn't, the formula grows to 55 bytes.

```
=LET(a,SUBSTITUTE(A1,"00",0),MID(a,SEQUENCE(LEN(a)),1))

```

---

If the output has to be an array but it can have trailing empty space, it's 47 bytes.

```
=MID(SUBSTITUTE(A1,"00",0),SEQUENCE(LEN(A1)),1)

```
> 2 votes

# Answer
# Vyxal, ~~6~~ 5 bytes

```
\0d0V

```

Try it Online!

-1 thx to @Steffan
> 2 votes

# Answer
# Thunno 2, 5 bytes

```
`000v

```

Attempt This Online!

#### Explanation

```
`000v  # Implicit input
`00    # Push "00"
   0   # Push 0
    v  # Replace "00" with "0"
       # Implicit output

```
> 2 votes

# Answer
# Nekomata, 4 bytes

```
ĭZĬ‼

```

Attempt This Online!

```
ĭZĬ‼        Take [1,0,0,1,0,0,1] as an example
ĭ       Uninterleave
            [1,0,0,1,0,0,1] -> [1,0,0,1] [0,1,0]
 Z      Check non-zero
            [0,1,0] -> [Failure,1,Failure]
  Ĭ     Interleave
            [1,0,0,1] [Failure,1,Failure] -> [1,Failure,0,1,0,Failure,1]
   ‼    Remove failures
            [1,Failure,0,1,0,Failure,1] -> [1,0,1,0,1]

```

The idea is to remove all zeros at odd positions (0-based).

The code makes use of the fact that Nekomata is lazy: `Z` will not fail immediately when it sees a zero, but only replace it with a "failure", that is, a nondeterministic object that has no value. Lists that contain failures can be used in most operations just like normal lists, and will only fail when they are printed as the final result. So we can safely interleave it with the original even-indexed part, and then remove all failures.
> 2 votes

# Answer
# C#, 191 bytes

```
string a(string s){var l=(s+'1').ToCharArray();s="";int b=0;for(int i=0;i<l.Length;i++){if(l[i]=='1'){if(b>0){s+=new string('0',b/2);b=0;}s+=l[i];}else b++;}return s.Substring(0,s.Length-1);}

```

Try it online!

It's neither clean nor short, but it works.

Takes input as a contiguous string of characters, outputs in the same format

Explanation:

```
string a(string s){                  //Define method a that takes input string s and returns a string
  var l=(s+'1').ToCharArray();       //Add a 1 to the end of s and split into char array l
  s="";                              //Empty s
  int b=0;                           //Initialize int b with value 0
  for(int i=0;i<l.Length;i++){       //Loop through l
    if(l[i]=='1'){                   //If current char is 1
      if(b>0){                       //If b is not 0
        s+=new string('0',b/2);      //Add half the amount of 0s we've counted to s
        b=0;                         //Reset b
      }                              //End if b is not 0
      s+=l[i];                       //Add current char to s
    }                                //End if current char is 1
    else b++;                        //If current char is not 1, increment b
  }                                  //End loop
  return s.Substring(0,s.Length-1);  //Return string minus last char
}                                    //End method

```

### Note

Yes I am aware this could simply be done using `s.Replace("00","0")`, my aim was to avoid using the obvious solution. After all, the whole point of PPCG is to have fun, right? ;)
> 1 votes

# Answer
# Swift - 65 bytes

```
func g(a:String){print(a.replacingOccurrences(of:"00",with:"0"))}

```

Usage: `g(a:"100100")`, obviously the I/O method is through strings.
> 1 votes

# Answer
# Pyth, 8 bytes

```
:z"00"\0

```

Try-it link.

Explanation:

```
:z"00"\0 Takes unquoted contiguous 1-line input.
 z       Initialized to unevaluated first input line (Q won't be any shorter)
  "00"   Matching regex pattern /00/g
      \0 Substitution string "0"
:        Regex find-and-replace

```
> 1 votes

# Answer
# Perl 5 8 + 1 (for -p flag) = 9 bytes

```
s/00/0/g

```

I made another answer because I liked my first one too much :)
> 1 votes

# Answer
# Awk - 18 bytes

First try doing anything with Awk so it might be possible to golf it more.

```
{gsub(00,0);print}

```

Usage: `echo "1001001" | awk '{gsub(00,0);print}'`
> 1 votes

# Answer
# Python 2, ~~84~~ 68 bytes

Not nearly as short as xnor's answer, but that's okay. I wanted to use `del`.

```
L=input()
i=0
while i<len(L):
 if L[i]<1:del L[i]
 i+=2-L[i]
print L

```

**Try it online**
> 1 votes

# Answer
# Pyth, 12 bytes

```
s.e?sbb*%k2b

```

Try this

Takes a quoted string.

I know there's a shorter Pyth answer already, but I thought someone might find this approach interesting/useful.

### Explanation

```
s.e?sbb*%k2b
 .e         Q  # enumerated map on the implicit input string. b=element; k = position
   ?sb         # Is that character nonzero? (Done by converting char to int.)
      b        # If yes, just return that character
        %k2    # Mod 2 of the position: 0 if even 1 if odd
       *   b   # Take b that many times: "" if even, "0" if odd
s              # Concat everything.

```

So every even "0" gets replaced by "".

### Similar, 13 bytes (12 bytes if it weren't for Pyth's unfortunate naming of map variables):

```
s.e?+%k2sbb""

```

Try that
> 1 votes

# Answer
## CJam, ~~20~~ 18 bytes

```
1l~]e`2/z~2ff/]z:~

```

Expects input as a list of bits, separated by spaces.

Explanation:

```
1   e# Push 1:              | 1
l   e# Read line:           | 1 "1 1 0 0 1 1 1 0 0 1 1"
~   e# Evaluate:            | 1 1 1 0 0 1 1 1 0 0 1 1
]   e# Wrap stack in array: | [1 1 0 0 1 1 1 0 0 1 1]
e`  e# Run-length encode:   | [[3 1] [2 0] [3 1] [2 0] [2 1]]
2/  e# Group by 2:          | [[[3 1] [2 0]] [[3 1] [2 0]] [[2 1]]]
z   e# Transpose:           | [[[3 1] [3 1] [2 1]] [[2 0] [2 0]]]
~   e# Unpack array:        | [[3 1] [3 1] [2 1]] [[2 0] [2 0]]
2ff/ e# Divide each by 2:   | [[[3 1] [3 1] [2 1]] [[1 0] [1 0]]]
]   e# Wrap stack in array: | [[[[3 1] [3 1] [2 1]] [[1 0] [1 0]]]]
z   e# Transpose:           | [[[3 1] [1 0]] [[3 1] [1 0]] [[2 1]]]
:~  e# Unpack each:         | [[3 1] [1 0] [3 1] [1 0] [2 1]]
e~  e# RLE decode:          | [1 1 1 0 1 1 1 0 1 1]
(;  e# Delete last element: | [1 1 0 1 1 1 0 1 1]
e# Implicit output: "110111011"

```

### Alternative (9 bytes):

```
l~[0_]/0*

```

Expects input as a CJam list literal.

Explanation:

```
l~   e# Read line and eval: | [1 1 0 0 1 1 1 0 0 1 1]
[0_] e# Push [0 0]:         | [1 1 0 0 1 1 1 0 0 1 1] [0 0]
/    e# Split array:        | [[1 1] [1 1 1] [1 1]]
0*   e# Join with 0:        | [1 1 0 1 1 1 0 1 1]

```
> 1 votes

# Answer
# ES7, 23 bytes

```
_=>_.replace(/00/g,`0`)

```

Input is string without whitespace + it allows odd lengths of runs of 0, it just keeps it as is.
> 1 votes

# Answer
# Zsh, 13 bytes

```
<<<${1//00/0}

```

Try it online!
> 1 votes

# Answer
# x86-16 machine code, 15 bytes

```
00000000: b401 aca8 0175 04f6 dc78 01aa e2f4 c3    .....u...x.....

```

Listing:

```
B4 01       MOV  AH, 1          ; set zero run counter flag set to positive
        CLOOP:
AC          LODSB               ; load next byte
A8 01       TEST AL, 1          ; is a 1 or 0?
75 04       JNZ  IS_ONE         ; if 1, store to output and loop
F6 DC       NEG  AH             ; flip sign of zero run counter flag
78 01       JS   ODD_ZERO       ; if negative, don't output
        IS_ONE:
AA          STOSB               ; copy char to output
        ODD_ZERO:
E2 F4       LOOP CLOOP          ; loop until end of input
C3          RET                 ; return to caller

```

Callable function, input array at `[SI]`, len in `CX`. Output to array at `[DI]`.

Test program output:

Try it online!
> 1 votes

# Answer
# Brainfuck, 51 bytes

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

```

Try It Online!

This program takes a string of `0`'s and `1`'s as input and prints a string of `0`'s and `1`'s as output.
> 1 votes

# Answer
# Husk, 6 bytes

```
σD;0;0

```

Try it online!

### Explanation

```
σD;0;0
σ       replace all                 with
 D                  2 copies of
  ;0                            [0]
    ;0                                   [0]

```
> 1 votes

# Answer
# Pari/GP, 21 bytes

```
a->[i|i<-q=a,i||q=!q]

```

Try it online!
> 1 votes

# Answer
# APOL, 33 bytes

`j(ƒ(i ¿(!(I(∋)) ¿(≐(∈) 0 '') 1)))`

Explanation:

```
j(            Join list to string
  ƒ(          List-builder for
    i         Get input
    ¿(        Returning if
      !(      Not
        I(    As number
          ∋   Loop item
        )
      )
              If true return
      ¿(      Returning if
        ≐(∈)  Loop counter is even
        0     If true return 0
        ''    Else return an empty string
      )
      1       Else return 1
    )
  )
)

```
> 1 votes

# Answer
# convey, 32 bytes

```
{">>>v
 "+."@}
1#,0=]
^>@<<
^<$1

```

Try it online!

How it works with input \[1,0,0,0,0,1\]:
> 1 votes

# Answer
# brainfuck, 23 bytes

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

```

Try it online!

```
,[         while(c=getchar()) {
  .++[       putchar(c);
    ->+++++< e=5*(c+2)
  ]
  >+[        if(e!=-1) {
    ,>         getchar();
  ]          }
,]         }

```
> 1 votes

# Answer
# Lexurgy, 10 bytes

Input is a string of `a`s and `b`s, where `a` is 1 and `b` is 0.

Finds two `b`s and replaces them with a `b` and an empty string.

```
a:
b b=>b *

```

Variant that does the same thing with actual `0` and `1` digits (12 bytes):

```
a:
\0\0=>\0 *

```
> 1 votes

# Answer
# Desmos, 28 bytes

```
f(L)=L[(L-1)^{[0...9999]}<1]

```

Takes input as a list of 0s and 1s, and returns a list of 0s and 1s.

This works by filtering for elements that are either 1, or 0 and with odd (0-based) index in the list.

Desmos lists have a maximum length of 10000 elements, so `[0...9999]` is a valid golf from `[0...L.length]`.

Try it on Desmos!
> 1 votes

# Answer
# AWK, 8 bytes

```
$0||NR%2

```

Try it online!

I found this nice solution following the thinking of this answer.

It's a simple OR gate used as a AWK pattern: it prints the line if the input is true (i.e., `1`) or it's an odd line (`NR` is the number of the line). It will skip only the `0` in even lines.

### AWK, 15 bytes (former answer)

```
gsub("00","0")1

```

Try it online!

Globally substitutes all `"00"` strings to `"0"`. The `1` in the end is a True token to force printing the line if there were no substitutions.
> 1 votes

# Answer
# Julia, 21 bytes

```
!x=replace(x,"00"=>0)
```

Attempt This Online!
> 1 votes

# Answer
# Wolfram Language (Mathematica), 22 bytes

```
Select[#>=(i=-i)&]
i=1

```

Try it online!
> 1 votes

# Answer
# Octave, 25 bytes

```
@(a)a(~mod(cumsum(~a),2))

```

Try it online!

Find the indices of even elements in the cumsum of the logical negation of the input.
> 1 votes

# Answer
# Uiua, 4 bytes

```
▽\=.

```

Try it!

Port of emanresu A's Vyxal answer.

```
▽\=.
   . # duplicate
 \=  # scan by equality
▽    # keep

```
> 1 votes

# Answer
# Perl 5 50 + 1 (for -p flag) = 51 bytes

```
@a=split'',$_;splice@a,$i++,!$_ for@a;$_=join'',@a

```
> 0 votes

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


title: Split into sublists of specified sizes

text:
# Question
Title: Split into sublists of specified sizes
05AB1E has the `£` builtin which, given a list of integers `b` and a string `s`, splits `s` into sublists of lengths equal to the elements in `b`. For example, `[1,2,3,4,1] "hello world"£` produces `["h", "el", "lo ", "worl", "d"]`. Your task is to imitate this behaviour.

Given a list \\$L\\$ containing \\$n\\$ elements, and a list \\$B\\$ of positive integers that sum to \\$n\\$, emulate the behaviour of `£` in 05AB1E. \\$L\\$ will always contain positive digits (so `123456789`), \\$n\\$ will always be greater than or equal to \\$1\\$ and will never exceed your language's maximum integer.

If you have a builtin which mimics this *exact* behaviour, such as 05AB1E's `£`, you may not use it. Every other builtin, including ones that partition the input into slices of a given integer length are acceptable. Essentially, any command that is not a standalone answer to this challenge is acceptable.

You may take the two lists in any convenient method or format, including taking \\$L\\$ as an integer. You may optionally take \\$n\\$ as input. You may output in any format that clearly shows the sublists of \\$L\\$, distinct from each other. For example, outputting integers separated by newlines, or outputting a list of lists of digits.

This is , so the shortest code in bytes wins.

## Test cases

```
L, B -> output
[[4, 5, 1, 2, 6, 1, 7, 9, 6], [2, 4, 3]] -> [[4, 5], [1, 2, 6, 1], [7, 9, 6]]
[[4, 2, 8, 7, 3, 5, 9, 3, 1, 9, 1, 8, 1, 7, 2, 8, 3, 7, 6], [1, 3, 1, 14]] -> [[4], [2, 8, 7], [3], [5, 9, 3, 1, 9, 1, 8, 1, 7, 2, 8, 3, 7, 6]]
[[8, 7, 4, 6], [1, 3]] -> [[8], [7, 4, 6]]
[[7], [1]] -> [[7]]
[[6, 4, 3, 8, 9, 3, 6, 5, 7, 8, 3, 2, 5, 1, 2], [3, 3, 3, 3, 3]] -> [[6, 4, 3], [8, 9, 3], [6, 5, 7], [8, 3, 2], [5, 1, 2]]
[[2, 7, 9, 3, 8, 1, 5], [4, 3]] -> [[2, 7, 9, 3], [8, 1, 5]]
[[1, 9, 8, 9, 6, 3, 4, 2, 3, 4, 1, 8, 5, 5, 2, 9, 3, 6, 7], [3, 1, 2, 13]] -> [[1, 9, 8], [9], [6, 3], [4, 2, 3, 4, 1, 8, 5, 5, 2, 9, 3, 6, 7]]
[[1, 8, 7, 8, 9, 4, 2, 5, 2, 7, 1, 5, 2, 3, 8, 4, 6, 9, 1, 9, 3, 4, 6, 7, 6, 5, 3], [7, 7, 3, 8, 2]] -> [[1, 8, 7, 8, 9, 4, 2], [5, 2, 7, 1, 5, 2, 3], [8, 4, 6], [9, 1, 9, 3, 4, 6, 7, 6], [5, 3]]
[[7, 4, 4, 7, 5, 5], [1, 2, 3]] -> [[7], [4, 4], [7, 5, 5]]
[[9, 2, 8, 7, 2, 3, 9, 5, 8, 1, 5, 2], [2, 2, 2, 2, 2, 1, 1]] -> [[9, 2], [8, 7], [2, 3], [9, 5], [8, 1], [5], [2]]
[[8, 7, 3], [3]] -> [[8, 7, 3]]
[[8, 2, 7, 3, 9, 5, 6, 9, 5, 3, 1, 9, 7, 5, 3, 6, 4, 1], [2, 1, 2, 6, 2, 2, 3]] -> [[8, 2], [7], [3, 9], [5, 6, 9, 5, 3, 1], [9, 7], [5, 3], [6, 4, 1]]
[[8, 2, 3, 7, 4, 7, 7, 4, 5, 5, 8, 1, 2, 3, 3], [3, 7, 4, 1]] -> [[8, 2, 3], [7, 4, 7, 7, 4, 5, 5], [8, 1, 2, 3], [3]]
[[4, 3, 8, 9, 9, 3, 2, 5, 5, 8, 2, 8, 1, 1, 4, 1], [10, 5, 1]] -> [[4, 3, 8, 9, 9, 3, 2, 5, 5, 8], [2, 8, 1, 1, 4], [1]]
[[6, 3, 2, 9, 5, 6, 1, 4, 9, 4, 2, 5, 6, 8, 8, 5], [4, 3, 2, 1, 2, 2, 2]] -> [[6, 3, 2, 9], [5, 6, 1], [4, 9], [4], [2, 5], [6, 8], [8, 5]]
[[2, 2, 1, 6, 8, 5, 2, 6, 7, 9, 4, 5, 8, 1, 9, 6, 3, 8, 7, 3, 9, 1], [6, 7, 1, 2, 2, 2, 2]] -> [[2, 2, 1, 6, 8, 5], [2, 6, 7, 9, 4, 5, 8], [1], [9, 6], [3, 8], [7, 3], [9, 1]]

```

# Answer
# Jelly, 3 bytes

```
Rṁ@

```

Try It Online!

Equivalently, `ṁR}` but with the arguments the other way around.

```
R    Range (vectorizes)
 ṁ@  Mold the right argument to the shape of the ranges

```

```
ṁ    Mold the left argument to the shape of:
 R}  Range (vectorizes) of the right argument

```
> 11 votes

# Answer
# Python 2, 39 bytes

```
lambda L,B:[map(L.pop,[0]*x)for x in B]

```

Try it online!
> 9 votes

# Answer
# 05AB1E, 5 bytes

I've tried to implement `£` manually way too often because the docs just say *`£` \- Head. Push `a[0:b]`*, which is exactly what this builtin does if you just pass a single integer.

```
L˜Å¡¦

```

Try it online!

`L` convert each length `n` into a range `[1 .. n]`
`˜` flatten into a list of integers
`Å¡` split the sequence on `1`'s (the only truthy value in 05AB1E)
`¦` remove the leading empty list that was created by splitting at index 0
> 8 votes

# Answer
# APL (Dyalog Extended), 3 bytes

-2 thanks to ovs!

```
⍸⍛⊆

```

How does it work?

Firstly `⍸2 4 3` is `1 1 2 2 2 2 3 3 3`.

We can then use this to partition () the right argument into chunks.

Try it online!
> 7 votes

# Answer
# , 6 bytes

```
</.~I.

```

Try it online!

Called with the list as left arg, grouping mask as right arg.

The whole thing is a dyadic hook, so that...

* `I.` applies only to the grouping mask, and expands it in place using unique elements. Eg, `I. 2 4 3` becomes:

```
0 0 1 1 1 1 2 2 2

```
* `</.~` That mask is used to group `/.` the list itself, putting each group into a box `<`.
> 6 votes

# Answer
# WolframLanguage (Mathematica), ~~28~~ 25 bytes

```
TakeDrop~FoldPairList~##&

```

–3 bytes from att.

Try it online!

With the prohibitied built-in (introduced in 2017 with v. 11.2), it's 8 bytes:

```
TakeList

```
> 6 votes

# Answer
# Python 2, 42 bytes

Inputs \\$ L \\$ and \\$ B \\$ as two comma separated lists from STDIN, and outputs sublists each on one line.

```
L,B=input()
for x in B:print L[:x];L=L[x:]

```

Try it online!
> 6 votes

# Answer
# \>= 4.1, ~~30~~ 29 bytes

```
\(L,B)split(L,rep(seq(!B),B))

```

Try it online!

An anonymous function taking two vectors and returning a list of vectors.

Thanks to @pajonk for saving a byte!
> 6 votes

# Answer
# JavaScript (ES6), 44 bytes

Expects `(a)(b)`.

```
a=>g=([v,...b])=>v?[a.splice(0,v),...g(b)]:b

```

Try it online!

(or **43 bytes** with linefeeds)
> 6 votes

# Answer
# Haskell, 34 bytes

```
(zipWith take<*>).scanl(flip drop)

```

Try it online!

`scanl(flip drop)` takes the input and sucessively drops off prefixes.

```
Prelude> scanl(flip drop) "Test string, test string, 123" [6,1,2,3]
[ "Test string, test string, 123"
, "tring, test string, 123"
, "ring, test string, 123"
, "ng, test string, 123"
, " test string, 123"
]

```

Note that the first result will always be the input string.

Once we have that we apply `zipWith take` to then take off the prefixes for each size.
> 6 votes

# Answer
# Brachylog, 7 bytes

```
~cʰ\l₎ᵐ

```

Try it online!

`~cʰ` split the left argument into groups, `\` transpose so we have a list of (group, length), `l₎ᵐ` map each pair: the right element is the length of the left element (which is also the output of `l`).
> 5 votes

# Answer
# Haskell, ~~35~~ 34 bytes

```
x?(c:d)=take c x:drop c x?d
x?_=[]

```

Try it online!

-1, thanks Wheat Wizard!
> 5 votes

# Answer
# Vyxal, 2 bytes

```
ɾ•

```

Try it Online!

~~If generators weren't so broken, it'd just be `vɾ•` and flagless.~~ Thank goodness for Vyxal 2.8 lol.

## Explained

```
ɾ•
ɾ    # vectorise range for each item in the shape list
•   # and mold that to the shape list

```

So essentially, a port of hyper's jelly
> 4 votes

# Answer
# Factor, 24 bytes

```
[ [ cut swap ] map nip ]

```

Try it online!

Mapping the lengths to the part of the input that gets 'cut off.' Cutting a sequence into two parts and getting at the results is efficient in bytes because both pieces just end up on the data stack, instead of locked away inside some collection. Process looks something like this:

1. `"hello world" { 1 2 3 4 1 }`
2. `"ello world" { "h" 2 3 4 1 }`
3. `"lo world" { "h" "el" 3 4 1 }`
4. `"world" { "h" "el" "lo " 4 1 }`
5. `"d" { "h" "el" "lo " "worl" 1 }`
6. `"" { "h" "el" "lo " "worl" "d" }`
7. `{ "h" "el" "lo " "worl" "d" }`
> 4 votes

# Answer
# Japt `-m`, 3 bytes

Takes `B` as the first input.

```
VvU

```

Try it

```
VvU     :Implicit map of each U in first input (B)
V       :Second input (L)
 vU     :Remove and return the first U elements

```
> 4 votes

# Answer
# K (ngn/k), 8 bytes

```
{.=x!&y}

```

Try it online!

Takes the list of values as `x` and the lengths of the chunks as `y`.

* `&y` convert length of chunks from e.g. `2 4 3` to `0 0 1 1 1 1 2 2 2`
* `x!` make a dictionary mapping the original input to these indices
* `=` "group" that dictionary (i.e., map the distinct values of the dictionary to their corresponding keys)
* `.` return just the values (i.e., the original values, split into chunks of the correct lengths)
> 4 votes

# Answer
# Stax, 3 bytes

```
m%s

```

Run and debug it

Takes a string of digits, and the partitions as an integer array.

outputs each slice with a newline.
> 3 votes

# Answer
# Ruby, 44 26 bytes

```
->b,l{b.map{|x|l.shift x}}

```

Try it online!

*-18 thanks to dingledooper*
> 3 votes

# Answer
# Charcoal, 10 bytes

```
≔⮌θθＥη⭆ι⊟θ

```

Try it online! Link is to verbose version of code. Outputs a newline-separated list of digit strings. Explanation:

```
≔⮌θθ

```

Reverse `L`.

```
Ｅη⭆ι⊟θ

```

For each element of `B`, pop that many elements from `L`, and concatenate the digits into a string for output.
> 3 votes

# Answer
# Scala, 64 bytes

```
s=>_./:(Seq[Any]()->s){case(a->s,x)=>(a:+s.take(x),s drop x)}._1

```

Try it online!

Called as `f(fullList)(sublistSizes)`

```
s =>   //The sequence of integers to be split
 _     //The sizes for it to be split into
  ./:  //Fold over it,
   (Seq[Any]()->s) //Starting with an empty list of sublists, and the original list
   {case(a->s,x) => //a is the current list of sublists, s is the current full list, x is the current element
    (a:+s.take(x),  //Add the first x elements of s as a sublist
     s drop x)      //Drop x elements from the full list
   }._1             //Only keep the list of sublists

```
> 3 votes

# Answer
# Desmos, ~~128~~ 117 bytes

```
a=length(B)
g(l)=\sum_{k=1}^{[1...length(l)]}l[k]
f=\prod_{n=1}^a\{g(B)[n]+n=[1...\length(L)+a]:0,1\}
h(L,B)=L[g(f)]f

```

Implements a function \\$h(L,B)\\$. Output is a list of numbers, with each sublist separated by a zero.

Try It On Desmos!

Try It On Desmos! - Verbose

### Explanation:

`a=length(B)`: A helper value that stores the length of the list `B` specified in the challenge description.

`g(l)=\sum_{k=1}^{[1...length(l)]}l[k]`: A helper function that returns the running total(as a list) of the list argument `l`.

`f=\prod_{n=1}^a\{g(B)[n]+n=[1...\length(L)+a]:0,1\}`: Creates a list of 0's and 1's, which will be used later to determine the format of the final outputted list(`0`'s mean sublist separator, `1`'s mean to put an element of `L` there, where `L` is specified in the challenge description.).

`h(L,B)=L[g(f)]f`: The actual function that outputs the answer, with each sublist separated by a zero.
> 3 votes

# Answer
# Python 3, 76 bytes

```
def f(x,n):x=iter(x);return[[*islice(x,a)]for a in n]
from itertools import*

```

Try it online!
> 2 votes

# Answer
# C (gcc), ~~65~~ 58 bytes

```
f(s,b,l)int*s,*b;{for(;l--;s+=*b++)printf("%.*ls ",*b,s);}

```

Try it online!

Inputs a pointer to a list of digits as a wide-character string, a pointer to a list of integer lengths and that list's length (since pointers in C carry no length info).
Outputs the sub-lists separated by spaces.
> 2 votes

# Answer
# Julia 1.0, ~~33~~ ~~30~~ 25 bytes

```
l/b=b.|>a->splice!(l,1:a)

```

Try it online!

Thanks to dingledooper for -3 bytes and to MarcMush to further -5.
> 2 votes

# Answer
# Husk, ~~5~~ 4 bytes

```
CmR¹

```

Try it online!

```
CmR¹      # 5-byte program, but this is equivalent to
CzR⁰⁰²    # 6-byte program using the ¹ shortcut to use the 1st arg twice and implicit 2nd arg
 m        # map over
   ⁰      # the list of the 1st argument
  R ⁰     # by repeating arg1 this number of times;
          # now use the lengths of this list of lists to
C    ²    # cut the list of the 2nd argument

```
> 2 votes

# Answer
# PowerShell Core, 39 bytes

```
param($u,$v)$u|%{,$v[$s..(($s+=$_)-1)]}

```

Try it online!

Two test cases are not working because PowerShell flattens simple jagged arrays, i.e. `[[7]]` becomes `[7]`
> 2 votes

# Answer
# Uiua, ~~5~~ 3 bytes

```
⊕□⊚

```

Try it!

-2 thanks to Bubbler

```
⊕□⊚
  ⊚  # where
⊕□   # group with boxing

```
> 2 votes

# Answer
# MATL, 5 bytes

```
"@:&)

```

Inputs *B*, then *L*. Displays each sublist on a separate line.

Try it online!

# Explanation

```
"      % Implicit input: numeric vector B. For each k in B
  @    %   Push k
  :    %   Range [1 2 ... k]
  &)   %   Two-ouput indexing. The first time this takes as implicit input
       %   the numeric vector L; in subsequent iterations it uses as input
       %   what remains of L. Pushes a smaller vector according to the
       %   specified indices, and another vector with the remaining entries
       % Implicit end. Implicit display stack

```
> 1 votes

# Answer
# Arturo, 36 bytes

```
$[a,b][map b'i[take a i a:drop a i]]

```

Try it

```
$[a,b][             ; a function taking two arguments a and b
  map b'i[          ; map over b and assign current elt to i
    take a i        ; the first i elts of a
    a:drop a i      ; assign a sans the first i elts to a
  ]                 ; end map
]                   ; end function

```
> 1 votes

# Answer
# Nekomata, 4 bytes

```
J$ᶻL

```

Attempt This Online!

```
J$ᶻL    Input L and R
J       Non-deterministically split L into parts
 $      Swap to get R
  ᶻL    Check that the length of each part is equal to the corresponding element of R

```
> 1 votes

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


title: Random factorized numbers

text:
# Question
Title: Random factorized numbers
# Input

The code should take an integer \\$n\\$ between 1 and 1000.

# Output

The code should output positive integers with \\$n\\$ bits. Accompanying each integer should be its full factorization. Each integer should be a uniformly random \\$n\\$ bit number.

# Score

The score for your code will be the number of integers it outputs, with their factorizations, in ten seconds on my Ubuntu PC when \\$n = 500\\$.

# Primality testing

If you need to test if a number is prime, you can use any method that is any of:

* Provably always correct
* Not proven to always be correct but for which there is no known example where it is incorrect
* Provably has probability at most \\$2^{-30}\\$ of giving the wrong answer.

As always,this challenge is *per* language and I will keep a scoreboard for the answers given.

# Is this possible?

The two best known methods are Bach's algorithm and a simpler one by Kalai.

# Leaderboard

* **4** in **Rust** by mousetail
* **500** in **Python 3.10** by Command Master
* **14406** in **C++** by Command Master

# Answer
# Python

Thanks to @AndersKaseorg for many improvements and bug fixes.

```
import math
import random
import time

import sympy

def gen_factor(N):
    while True:
        j = random.randint(1, N.bit_length() - 1)
        q = (1 << j) + random.randrange(1 << j)
        if q > N:
            continue
        Nt = N // q
        if random.random() >= math.log(q, N) * (((Nt + 1) >> 1) << j) / N:
            continue
        p, a = sympy.perfect_power(q) or (q, 1)
        if random.random() >= 1 / a:
            continue
        if sympy.isprime(p):
            return p, a, Nt

def bach(N):
    if N <= 10 ** 5:
        x = random.randint(N//2 + 1, N)
        return x, sympy.factorint(x)
    while True:
        p, a, Nt = gen_factor(N)
        newx, factx = bach(Nt)
        newx *= p ** a
        if random.random() < math.log(N / 2, newx):
            factx[p] = factx.get(p, 0) + a
            return newx, factx

def gen(n):
    return bach((1 << n) - 1)

if __name__ == '__main__':
    t = time.perf_counter()
    a = []
    while time.perf_counter() - t < 10:
        a.append(gen(500))

    print('Generated', len(a), 'numbers in 10 seconds:')
    print(*a, sep='\n')

```

Attempt This Online!

This is a simple implementation of Bach's algorithm, just to get the challenge going. Make sure you have `gmpy2` installed when running. Can generate around \\$130\\$ numbers on my computer.
> 6 votes

# Answer
# C++ (gcc), score = 14406

```
#include <vector>
#include <chrono>
#include <cassert>
#include <map>
#include <random>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <gmp.h>
#include <gmpxx.h>

std::minstd_rand rng;
gmp_randstate_t gmp_rng;
double prob[1011];
const int maxV = 510510;
#define Vfactors {2, 3, 5, 7, 11, 13, 17}
const int sqrtV = 715;
int sieve[maxV+1];
int primeps[maxV];
int primecnt = 0;
double logpq_sum[maxV];
int coprimes[92160];
std::uniform_int_distribution<> coprime_dist(0, 92159);
int coprimecnt = 0;
const double RAT = 510510. / 92160;
const double LOGV = 18.96157969569485;

void gen_factor(mpz_t N, int Nexp, double Nbase, mpz_t q, long int* qexp, double* qbase, mpz_t p, int* a, mpz_t Nq) {
    const double invN = 1 / Nbase;
    const double Nlog2 = Nexp + log2(Nbase);
    int I;
    for (I = 0; ; I++) {
        int i = I;
        double div = ldexp(invN*maxV, i-Nexp);
        if (div >= 1) break;
        prob[I] = (LOGV + i)*(1 + 1/(ldexp(maxV, i)-1)) + div*Nlog2;
    }
    int directI = I;
    const double finvN = ldexp(invN, -Nexp);
    prob[I++] = RAT * (logpq_sum[primecnt-1] + finvN * Nlog2 * (primecnt-1)); // small prime powers
    std::discrete_distribution<> distribution(std::begin(prob), std::begin(prob)+I);
    while (1) {
        int J = distribution(rng);
        if (J < directI) {
            const int i = J;
            mpz_urandomb(p, gmp_rng, i);
            mpz_setbit(p, i);
            mpz_mul_ui(p, p, maxV);
            mpz_add_ui(p, p, coprimes[coprime_dist(rng)]);
            if (mpz_cmp(p, N) > 0) continue;

            long pexp;
            double pbase = mpz_get_d_2exp(&pexp, p);

            double p_d = mpz_get_d(p);

            *a = 0;

            double logp = pexp + log2(pbase);
            double Nlogp = Nlog2 / logp;

            double choice_probability = (LOGV + i) / logp + Nlogp * finvN * (ldexp(maxV, i) - 1);

            #ifdef DEBUG
            std::cout << choice_probability << '\n';
            #endif

            double f = std::uniform_real_distribution<>(0, choice_probability)(rng);

            while (*a <= Nlogp && f >= 0) {
                ++*a;
                f -= (ldexp(maxV, i) - 1) * pow(p_d, -*a) + (ldexp(maxV, i) - 1)*finvN;
            }

            if (*a > Nlogp) continue;

            if (!mpz_probab_prime_p(p, 15)) continue;

            mpz_pow_ui(q, p, *a);
        } else { // small prime
            double f = std::uniform_real_distribution<>(0, logpq_sum[primecnt-1] + finvN * Nlog2 * (primecnt-1) )(rng);
            int l = 0;
            int r = primecnt-2;
            int ans = primecnt-1;
            while (l <= r) {
                int m = (l + r) / 2;
                double v = logpq_sum[m] + finvN * Nlog2 * m;
                if (v >= f) {
                    ans = m;
                    r = m-1;
                } else {
                    l = m+1;
                }
            }
            int pv = primeps[ans];
            mpz_set_ui(p, pv);

            double Nlogq = Nlog2 / log2(pv);

            f = std::uniform_real_distribution<>(0, 1 + Nlogq * (pv-1) * finvN )(rng);

            *a = 0;

            while (*a <= Nlogq && f >= 0) {
                ++*a;
                f -= (pv-1) * (pow(pv, -*a) + finvN);
            }

            if (*a > Nlogq) continue;

            mpz_ui_pow_ui(q, pv, *a);
        }

        *qbase = mpz_get_d_2exp(qexp, q);

        mpz_fdiv_q(Nq, N, q);
        int is_odd = mpz_odd_p(Nq);
        if (is_odd) mpz_add_ui(Nq, Nq, 1);
        double Nqd = mpz_get_d(Nq);
        if (!std::bernoulli_distribution(Nqd / (ldexp(Nbase / *qbase, Nexp - *qexp) + 1))(rng)) continue;
        if (is_odd) mpz_sub_ui(Nq, Nq, 1);
        return;
    }
}

void bach(mpz_t v, mpz_t target, std::vector<mpz_class>& factors) {
    if (mpz_cmp_ui(v, 1e7) < 0) {
        unsigned int vI = mpz_get_ui(v);
        int x = std::uniform_int_distribution<>(vI/2+1, vI)(rng);
        mpz_set_ui(target, x);
        factors.clear();
        for (int d = 2; d*d <= x; d++) {
            while (x % d == 0) {
                factors.emplace_back(d);
                x /= d;
            }
        }
        if (x != 1) {
            factors.emplace_back(x);
        }
        return;
    }
    mpz_t q, p, Nt;
    mpz_inits(q, p, Nt, 0);
    long int Nexp;
    double Nbase = mpz_get_d_2exp(&Nexp, v);
    while (1) {
        int a;
        long int qexp;
        double qbase;
        gen_factor(v, Nexp, Nbase, q, &qexp, &qbase, p, &a, Nt);
        bach(Nt, target, factors);
        long int targetexp;
        double targetbase = mpz_get_d_2exp(&targetexp, target);
        double logv = (log2(Nbase) + Nexp - 1)/(log2(qbase) + qexp + log2(targetbase) + targetexp);
        if (std::bernoulli_distribution(logv)(rng)) {
            for (int i = 0; i < a; i++) factors.emplace_back(p);
            mpz_mul(target, target, q);
            mpz_clears(q, p, Nt, 0);
            return;
        }
    }
}

void gen(int n, mpz_t target, std::vector<mpz_class>& factors) {
    mpz_t v;
    mpz_init2(v, n);
    mpz_setbit(v, n);
    mpz_sub_ui(v, v, 1);
    bach(v, target, factors);
}

int main() {

    rng.seed(time(0));
    gmp_randinit_lc_2exp_size(gmp_rng, 64);
    time_t end = time(0) + 10;
    sieve[0] = sieve[1] = 1;
    for (int v : Vfactors) {
        for (int i = v; i <= maxV; i += v) sieve[i] = 1;
    }
    for (int i = 1; i < maxV; i++) if (!sieve[i]) coprimes[coprimecnt++] = i;
    for (int v : Vfactors) sieve[v] = 0;
    double logpq_sum_v = 0;
    for (int v = 2; v <= maxV; v++) {
        if (!sieve[v]) {
            if (v <= sqrtV)
            for (int i = v*v; i <= maxV; i += v) sieve[i] = 1;
            logpq_sum[primecnt] = logpq_sum_v += log2(v) / (v-1);
            primeps[primecnt++] = v;
        }
    }
    int i;
    int tsz = 0;
    int primecnt = 0;
    for (i = 0; time(0) <= end; i++) {
        mpz_t target;
        mpz_init(target);
        std::vector<mpz_class> factors;
        gen(500, target, factors);
        tsz += factors.size();
        if (factors.size() == 1) primecnt++;
        #ifdef OUTPUT
        mpz_out_str(stdout, 10, target);
        printf(" = ");
        for (int j = 0; j < factors.size(); j++) {
            if (j) printf(" * ");
            std::cout << factors[j];
        }
        printf("\n");
        #endif
        mpz_clear(target);
    }
    std::cout << "generated " << i << " numbers\n";
    std::cout << "prime probability " << primecnt/double(i) << ", expected apprx. " << 0.0028879 /* (Li(2^500) - Li(2^499)) / 2^499 */ << '\n';
    std::cout << "average number of prime divisors " << tsz/double(i) << " expected apprx. " << log(500 * M_LN2) + 1.0345 /* B_2, see Wikipedia */ << '\n';

}

```

Try it online!

Can output around 15,000 numbers on my computer. Compile with `-lgmp -lgmpxx -O3`. Please make sure there aren't other programs active while running this, because I've noticed that on my computer it changed the number by almost 1,000, even with just Firefox.

## Explanation

This is an implemention of Bach's algorithm, although with a lot of optimizations.

The main function is `gen_factor`, which given \\$n\\$ returns \\$q = p^\alpha\\$ with probability \\$\log(p) \\#(\frac{n}{2q}, \frac nq\] = \log(p) \lfloor\frac{\frac{N}{q} + 1}2\rfloor\\$, where \\$\\#(a, b\]\\$ is the number of integers in that range.

We approximate that the floor isn't important, and then use rejection sampling to get back the appropriate distribution.

After multiplying by (the constant) \\$\frac2N\\$, we get \\$\log(p)(\frac1q+\frac1N)\\$. Now we group the terms by \\$p\\$, and for a given \\$p\\$ we have its probability being $$\log(p) \sum\_{\alpha=1}^{\lfloor \log\_p(N) \rfloor} (\frac1{p^\alpha}+\frac1N) = \log(p) (\frac1{p-1} - \frac1{p^{\lfloor \log\_p(N) \rfloor}} + \frac{\lfloor \log\_p(N) \rfloor}N) \leq \frac{\log(p)}{p-1} + \frac{\log(N)}{N}$$

We split the range to \\$\[2, 510510)\\$, and \\$\[510510 \cdot2^i, 510510 \cdot2^{i+1})\\$ for all \\$i\\$. For the first range, we precalculate stuff to get numbers with the correct probability. For each of the \\$\[510510 \cdot2^i, 510510 \cdot2^{i+1})\\$ ranges we notice that the probability is decreasing, so we can just take the probability for \\$p = 510510\cdot 2^i\\$ and use rejection sampling. To lower the amount of numbers we have to generate, we require the numbers to be coprime to \\$510510 = 2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\\$, so we need to multiply the probability by \\$\frac{510510}{\varphi(510510)}\\$ for the other segment.
> 4 votes

# Answer
# Rust + rand + bnum, score=4 on my PC

Basic implementation of Kalai's algorithm. Apparently it's not very good. The random rejection at the end rejects 99% of candidates so makes it take a lot longer.

```
use bnum::BUint;
use rand::{distributions::uniform::UniformSampler, Rng};

#[inline]
fn mod_exponentiate(mut base: BUint<16>, mut exponent: BUint<16>, modulus: BUint<16>) -> BUint<16> {
    if modulus == (1u64).into() {
        return 0u64.into();
    }

    let mut result: BUint<16> = (1u64).into();

    while !exponent.is_zero() {
        if exponent.digits()[0] & 1 == 1 {
            result = result * base % modulus
        }
        exponent >>= 1;
        base = (base * base) % modulus
    }

    return result;
}

#[inline]
fn miller_test(candidate: BUint<16>, mut d: BUint<16>, witness: BUint<16>) -> bool {
    let mut x = mod_exponentiate(witness, d, candidate);

    if x == (1usize).into() || x == candidate - BUint::<16>::from(1u64) {
        return true;
    }

    while d != candidate - BUint::<16>::from(1u64) {
        x = (x * x) % candidate;
        d <<= 1;

        if x == (1u64).into() {
            return false;
        }

        if x == candidate - BUint::<16>::from(1u64) {
            return true;
        }
    }

    return false;
}

#[inline]
fn prime_test(candidate: BUint<16>, iterations: usize, rng: &mut rand::rngs::ThreadRng) -> bool {
    if candidate == BUint::ONE {
        return false;
    }
    if candidate == BUint::TWO {
        return true;
    }
    if candidate == BUint::THREE {
        return true;
    }
    if candidate.digits()[0] & 1 == 0 {
        return false;
    }

    let mut d = candidate - BUint::<16>::from(1u64);
    if !d.is_zero() {
        d >>= d.trailing_zeros();
    }

    let distribution =
        bnum::random::UniformInt::<BUint<16>>::new(BUint::TWO, &(candidate - BUint::TWO));

    for _ in 0..iterations {
        let witness = distribution.sample(rng);
        if !miller_test(candidate, d, witness) {
            return false;
        }
    }

    return true;
}

#[inline]
fn kalai_algorithm(max: BUint<16>, rng: &mut rand::rngs::ThreadRng) -> (Vec<BUint<16>>, BUint<16>) {
    loop {
        let mut candidates: Vec<BUint<16>> = vec![];

        while candidates.last() != Some(&BUint::ONE) {
            candidates.push(rng.gen_range(BUint::ONE..*candidates.last().unwrap_or(&max)))
        }

        candidates.retain(|candidate| prime_test(*candidate, 8, rng));

        if let Some(possible_output) = candidates.iter().cloned().reduce(|a, b| (a * b).min(max)) {
            if possible_output < max && rng.gen_range(BUint::ONE..max) < possible_output {
                break (candidates, possible_output);
            }
        }
    }
}

fn main() {
    let start_time = std::time::Instant::now();
    let max = BUint::ONE << 500;

    let threads: Vec<_> = (0..8)
        .map(|thread_id| {
            std::thread::spawn(move || {
                let mut rng = rand::thread_rng();
                loop {
                    let (factors, product) = kalai_algorithm(max, &mut rng);
                    if std::time::Instant::now() - std::time::Duration::from_secs(10) > start_time {
                        break;
                    }
                    println!("{thread_id}\t{product:?} {factors:?}")
                }
            })
        })
        .collect();

    threads.into_iter().for_each(|i| i.join().unwrap());
}

```

Run with:

```
opt-level=3
lto=true
panic="abort"

```
> 4 votes

# Answer
# Charcoal, 66 bytes, score 0 (usually)

```
≔Ｘ²ＮθＷ¹«≔⟦⊕‽⊖θ⟧υＷ⊖⌊υ⊞υ⊕‽⌊υ≔Φυ▷”8±cGＮºb6﹪←”κυ¿∧‹Πυθ‹‽θΠυ«⟦Ｉ⊞ＯυΠυ⟧Ｄ⎚

```

Try it online! Link is to verbose version of code with extra check because the version of Charcoal on TIO returns `None` for the product of an empty list and I can't use the version of Charcoal on ATO for multiple reasons. Note that you need to interrupt (`^C` if running locally or TIO's button) the code manually after ten seconds otherwise it will never print anything. Explanation: Uses Kalai's inefficient algorithm.

```
≔Ｘ²Ｎθ

```

Get `2ⁿ`.

```
Ｗ¹«

```

Repeat forever.

```
≔⟦⊕‽⊖θ⟧υ

```

Start with a random integer between `0` and `2ⁿ` exclusive.

```
Ｗ⊖⌊υ

```

Until a `1` is generated...

```
⊞υ⊕‽⌊υ

```

... push a random integer between `1` and the previous integer to the list.

```
≔Φυ▷”8±cGＮºb6﹪←”κυ

```

Filter out all non-primes from the list.

```
¿∧‹Πυθ‹‽θΠυ«

```

If the product is less than `2ⁿ` and passes a random chance, then...

```
⟦Ｉ⊞ＯυΠυ⟧Ｄ⎚

```

... output the primes and their product.

83 bytes for a version that times itself:

```
≔Ｘ²Ｎθ≔▷clock⟦⟧ηＷ‹⁻▷clock⟦⟧ηχ«≔⟦⊕‽⊖θ⟧υＷ⊖⌊υ⊞υ⊕‽⌊υ≔Φυ▷”8±cGＮºb6﹪←”κυ¿∧‹Πυθ‹‽θΠυ⟦Ｉ⊞ＯυΠυ

```

Try it online! Link is to verbose version of code with extra check because the version of Charcoal on TIO returns `None` for the product of an empty list and I can't use the version of Charcoal on ATO because it doesn't have access to `sympy.isprime`. Note that the timing is approximate and might generate an extra result which actually finished outside the desired time.

64 bytes for a version that finds one factorisation and exits:

```
⊞υＸ²Ｎ≔⊖⌈υθＷ∨›Πυθ›‽θΠυ«≔⟦⊕‽θ⟧υＷ⊖⌊υ⊞υ⊕‽⌊υ≔Φυ▷”8±cGＮºb6﹪←”κυ»Ｉ⊞ＯυΠυ

```

Try it online! Link is to verbose version of code. Still usually crashes out because it can't calculate the product of an empty list, and even when it does find a result, it usually takes more than 10 seconds, but just in case, here's a bash script that restarts the program on error and times out after 10 seconds: Try it online!
> 2 votes

# Answer
## Jelly (12 bytes) Score: 0

Edit: old code was wrong

> 2\*³XȮÆ!Ṅ ç1¿

New code: 2\*³XȮÆEṄ \>! ç1¿

```
2*³..... 2^input
...X.... Pick a random number in [0, 2^input)
....Ȯ... Print the random number
.....ÆE. Factorize it
.......Ṅ Print the factors and go to line
ç1¿..... Loop the function above forever

```

Old code:

> Jelly beginner, the code can likely be shortened. It generated 141'808 random numbers between \[0, 2^500) in 10 seconds on my MacBook Pro M2, the generated filesize is 68Mb. Try the code here: https://tio.run/##ASAA3/9qZWxsef//MirCs1jIrsOGIeG5hArDpzHCv////zUwMA

New code has a score of 0.

Testing code:

```
> ./jelly fu prime.jelly 500 > primelist.txt & pid=$!; sleep 10; kill $pid
> wc -l primelist.txt

```
> -3 votes

---
Tags: math, number-theory, fastest-code, probability-theory, factoring
---