title: CGAC2022 Day 25: When The Planets Align

text:
# Question
Title: CGAC2022 Day 25: When The Planets Align
Part of the **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

As a Christmas gift, you were given a toy solar system. In this toy, all the orbits are circular and happen in the same plane. Each planet starts at a fixed location, has a fixed circumference orbit, and moves at a fixed speed (all in the same direction). You want to figure out, given these variables, at what time all of the planets will align (relative to the star which they orbit).

For example, if we had three planets with rings of size 4, 8, and 12, and the planets started in positions 2, 1, and 0 respectively, it would look like this:

## The challenge

You are given three lists of non-negative integers, which are each \\$n\>1\\$ items long:

* \\$R\_x\\$, indicating the circumference of orbit for planet \\$x\\$ (will not be zero)
* \\$P\_x\\$, indicating the start position of planet \\$x\\$ (positions are zero-indexed; you can assume \\$P\_x \< R\_x\\$ for all \\$x\\$)
* \\$S\_x\\$, indicating the number of units that planet \\$x\\$ moves along its orbit

(You may also take these as a collection of 3-tuples \\$(R\_x, P\_x, S\_x)\\$ or a permutation thereof.)

Starting from \\$t=0\\$, after each time step, each planet moves \\$S\_x\\$ units around their orbit (i.e. \\$P\_x \leftarrow (P\_x + S\_x) \mod R\_x\\$). Your goal is to find the *smallest* time \\$t\\$ where \\$P\_x / R\_x \\$ of all the planets are the same, i.e. the smallest \\$t\\$ such that $$((P\_1 + t * S\_1) \mod R\_1) / R\_1 = ((P\_2 + t * S\_2) \mod R\_2) / R\_2 = \ldots = ((P\_n + t * S\_n) \mod R\_n) / R\_n$$ . You may assume that such a time exists.

## Test cases

| \\$R\\$ | \\$P\\$ | \\$S\\$ | \\$t\\$ |
| --- | --- | --- | --- |
| \\$\[1,1\]\\$ | \\$\[0,0\]\\$ | \\$\[0,0\]\\$ | \\$0\\$ |
| \\$\[100,100\]\\$ | \\$\[1,0\]\\$ | \\$\[1,0\]\\$ | \\$99\\$ |
| \\$\[4,8,12\]\\$ | \\$\[0,1,0\]\\$ | \\$\[1,5,3\]\\$ | \\$5\\$ |

Standard loopholes are forbidden. Shortest code wins.

# Answer
# Vyxal, 11 bytes

```
?*?+?~%/≈)ṅ

```

Try it Online!

```
          ṅ # First integer
---------)  # where...
?*          # Multiply by speeds
  ?+        # Add initial positions
    ?~%     # Modulo by orbit sizes, without popping
       /    # Divide by orbit sizes
        ≈   # Are they all equal?

```
> 9 votes

# Answer
# Pip, 24 bytes

```
W$!=:{(b+c*i)%a/a}MUaUii

```

Try It Online!

Takes inputs as a list of lists/tuples for each planet. Explanation:

```
W                   # While
 $!=:               # Fold not-equal of
     {(b+c*i)%a/a   # The planet position formula
     }MUa           # Mapped over all input tuples
 Ui                 # Increment i
i                   # Return i once the loop is exited

```
> 2 votes

# Answer
# Python NumPy, 46 bytes

```
f=lambda R,P,S:(P/R).ptp()and 1+f(R,(P+S)%R,S)

```

Attempt This Online!

Expects 3 NumPy arrays. May (will) have floating point issues. Does the test cases ok, though. Assumes time moves in steps (in other words the solution is a nonnegative integer) which OP seems to imply.

#### How?

Simple brute force. Proceed time step by time step.
> 2 votes

# Answer
# PARI/GP, 53 bytes

```
f(r,p,s,i)=if(#Set([p[i++]%x/x|x<-r])>1,1+f(r,p+s,s))

```

Attempt This Online!
> 2 votes

# Answer
# Thunno 2, 7 bytes

```
Ƙ×+Œ⁶/ạ

```

Try it online!

#### Explanation

```
Ƙ×+Œ⁶/ạ  # Implicit input
Ƙ        # First integer where:
 ×       #  Multiply by the first input
  +      #  Add to the second input
   Œ     #  Modulo by the third input
    ⁶/   #  Divide by the third input
      ạ  #  Are they all equal?
         # Implicit output

```
> 2 votes

# Answer
# Python, 83 bytes

```
f=lambda R,P,S,t=0:1<len({(p+s*t)%r/r for r,p,s in zip(R,P,S)})and f(R,P,S,t+1)or t

```

Attempt This Online!

Recursive function, takes input lists \\$R\\$, \\$P\\$ and \\$S\\$.
> 1 votes

# Answer
# Charcoal, 38 bytes

```
≔×÷Πθθηη≔×÷ΠθθζζＷ›⌈η⌊η«ＵＭη﹪⁺κ§ζλΠθ→»Ｉⅈ

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
≔×÷Πθθηη≔×÷Πθθζζ

```

Scale `P` and `S` so that their `R` value becomes the product of the initial `R` values.

```
Ｗ›⌈η⌊η«

```

Until the `P` values are equal, ...

```
ＵＭη﹪⁺κ§ζλΠθ

```

... add the `S` values to them modulo the `R` product, and...

... keep track of the time.

```
»Ｉⅈ

```

Output the final time.
> 1 votes

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

```
Z=>g=t=>Z.some(x=v=>x-(x=(v.P+~~t*v.S)%v.R/v.R))&&1+g(-~t)

```

Try it online!

# JavaScript (Node.js), 60 bytes

```
Z=>(g=t=>Z.some(x=v=>x-(x=(v.P+t*v.S)%v.R/v.R))&&1+g(-~t))``

```

Try it online!

# JavaScript (Node.js), 68 bytes

```
(R,P,S)=>(g=t=>R.some(x=(v,i)=>x-(x=(P[i]+t*S[i])%v/v))&&1+g(-~t))``

```

Try it online!

Thank tsh for -2 bytes

No floating issue
> 1 votes

# Answer
# 05AB1E, ~~13~~ 12 bytes

```
∞<.Δ*²+¹%¹/Ë

```

Try it online or verify all test cases.

**Explanation:**

```
∞            # Push an infinite list of positive integers: [1,2,3,...]
 <           # Decrease it to a non-negative list: [0,1,2,...]
  .Δ         # Pop and find the first which is truthy for:
    *        #  Multiply the third† (implicit) input-speeds to the value
     ²+      #  Add the second input starting positions
       ¹%    #  Modulo it by the orbit sizes
         ¹/  #  Then divide that by the orbit sizes
           Ë #  Check if all values in the list are the same
             # (after which the found integer is output implicitly as result)

```

† -1 byte removing the explicit third input builtin `³`. This will cause the very first iteration (for \\$n=0\\$) to multiply by the (implicit) first input orbit-sizes instead of intended third input-speeds, but this is irrelevant since it'll be a list of \\$0\\$s anyway for \\$n=0\\$. Every other iteration (\\$n\>1\\$) will multiply by the intended (implicit) third input-speeds.
> 1 votes

# Answer
# x86 32-bit machine code, 39 bytes

```
31 C0 48 40 60 92 96 31 FF 31 ED AD 93 AD 52 F7 E2 03 06 F7 F3 92 97 F7 E3 93 95 F7 E7 5A 39 D8 AD E1 E8 61 75 DD C3

```

Try it online!

Following the `fastcall` calling convention, this takes an array of triples of 32-bit integers in the order \\$R\_x,S\_x,P\_x\\$, taking the length in ECX and the address in EDX.

---

This works by iterating through all values of \\$t\\$ and checking them.

To do the checking, each planet's fractional position is calculated and cross-multiplied with the previous fraction in order to check if the fractions are equal. The previous fraction is initialised to 0/0, which functions as being equal to anything.

---

In assembly:

```
f:
    xor eax, eax    # Set EAX to 0. EAX will hold the current time, t.
    dec eax         # Subtract 1 from EAX to cancel out the next instruction.
nexttime:
    inc eax         # Add 1 to EAX, advancing t.
    pushad          # Save all general-purpose registers' values onto the stack.
    xchg edx, eax   # Switch the array address into EAX and t into EDX.
    xchg esi, eax   # Switch the array address into ESI.
    xor edi, edi    # Set EDI (for the last numerator) to 0.
    xor ebp, ebp    # Set EBP (for the last denominator) to 0.
nextplanet:
    lodsd           # Load R_x into EAX, advancing the pointer.
    xchg ebx, eax   # Switch R_x into EBX.
    lodsd           # Load S_x into EAX, advancing the pointer.
    push edx        # Save the value of EDX (t) onto the stack.
    mul edx         # Multiply EAX by EDX, producing t*S_x.
                    # (Also, the high half of the product goes in EDX;
                    #   we're assuming the values fit in 32 bits, so that's 0.)
    add eax, [esi]  # Add P_x to EAX, producing P_x+t*S_x.
    div ebx         # Divide EDX:EAX by EBX (R_x). The quotient goes in EAX
  #  and the remainder, the numerator of this planet's fractional position, goes in EDX.
    xchg edx, eax   # Switch this numerator into EAX.
    xchg edi, eax   # Switch this numerator into EDI and the last numerator into EAX.
    mul ebx         # Multiply the last numerator by this denominator (into EDX:EAX).
    xchg ebx, eax   # Switch the product into EBX and this denominator into EAX.
    xchg ebp, eax   # Switch this denominator into EBP and the last denominator into EAX.
    mul edi         # Multiply the last denominator by this numerator (into EDX:EAX).
    pop edx         # Restore the value of t from the stack into EDX.
    cmp eax, ebx    # Compare the two products.
    lodsd           # Load P_x into EAX, advancing the pointer.
    loope nextplanet  # Decrease ECX by 1, counting down from the number of planets.
                      #  Jump back if the result is nonzero and the comparison was equal.
    popad           # Restore all general-purpose registers' values from the stack.
    jne nexttime    # Jump if the comparison was not equal.
    ret             # Return. (The time t in EAX is the return value.)

```
> 1 votes

# Answer
# , 41 bytes

```
f=\(r,p,s)sum(if(sd(p%%r/r))1+f(r,p+s,s))

```

Attempt This Online!
> 1 votes

# Answer
## Pascal, 345 Bytes

This `function` requires a processor supporting at least Standard Pascal as defined in ISO standard 7185 (level 1).

```
type Z=integer;W=0..maxInt;P=record R,P,S: W end;function f(S:array[m..n:Z]of P):W;var t:W;i:Z;function a:Boolean;var i:Z;d:real;function q(i:Z):real;begin q:=S[i].P/S[i].R end;begin d:=0;for i:=m+1 to n do d:=d+abs(q(i)-q(i-1));a:=d=0 end;begin t:=0;while not a do begin t:=t+1;for i:=m to n do begin with S[i]do P:=(P+S)mod R end;end;f:=t end;

```

Readable/ungolfed version:

```
program planetaryAlignment(output);
    type
        integerNonNegative = 0..maxInt;
        planet = record
                circumference: integerNonNegative;
                start: integerNonNegative;
                speed: integerNonNegative
            end;
    var
        { test planetary systems }
        A, B: array[1..2] of planet;
        C:    array[1..3] of planet;

    { In this subroutine `system[i].start` means “current position.” }
    function planetaryAlignment(
            system: array[minimum..maximum: integer] of planet
        ): integerNonNegative;
        var
            { discrete time step }
            t: integerNonNegative;
        { checks whether all planets are aligned on a line }
        function aligned: Boolean;
            var
                i: integer;
                { accumulates differences in positions }
                delta: real;
            { planetary position expressed as cycles }
            function position(i: integer): real;
                begin
                    with system[i] do
                    begin
                        position := start / circumference
                    end
                end;
            begin
                delta := 0.0;

                for i := minimum + 1 to maximum do
                begin
                    delta := delta + abs(position(i) - position(i - 1))
                end;

                aligned := delta = 0.0
            end;
        { advance planetary system by a simulation step }
        procedure simulate;
            var
                i: integer;
            begin
                t := t + 1;

                for i := minimum to maximum do
                begin
                    with system[i] do
                    begin
                        start := (start + speed) mod circumference
                    end
                end
            end;
        { simulation loop until alignment condition is met }
        begin
            t := 0;

            while not aligned do
            begin
                simulate
            end;

            planetaryAlignment := t
        end;

    { ─── MAIN ──────────────────────────────────────────────────────────── }
    begin
        A[1].circumference :=   1; A[1].start :=   0; A[1].speed :=   0;
        A[2].circumference :=   1; A[2].start :=   0; A[2].speed :=   0;
        writeLn(planetaryAlignment(A));

        B[1].circumference := 100; B[1].start :=   1; B[1].speed :=   1;
        B[2].circumference := 100; B[2].start :=   0; B[2].speed :=   0;
        writeLn(planetaryAlignment(B));

        C[1].circumference :=   4; C[1].start :=   0; C[1].speed :=   1;
        C[2].circumference :=   8; C[2].start :=   1; C[2].speed :=   5;
        C[3].circumference :=  12; C[3].start :=   0; C[3].speed :=   3;
        writeLn(planetaryAlignment(C));
    end.

```
> 0 votes

# Answer
# Japt v2.0a0, 21 bytes

Takes input in the order `P`, `S`, `R`.

```
@í+Vm*X)íuW í÷W äÎd}f

```

Try it
> 0 votes

# Answer
# Scala, 158 bytes

\\$ \color{red}{\text{Failed on the last case, I have no idea how to correct it.}} \\$

---

Golfed version. Try it online!

```
def f(r:Seq[Int],p:Seq[Int],s:Seq[Int],i:Int):Int={if(r.indices.exists(index=>p(i%p.length)%r(index)!=0)){1+f(r,p.zip(s).map{case (pi,si)=>pi+si},s,0)}else 0}

```

Ungolfed version. Try it online!

```
object Main {
  def main(args: Array[String]): Unit = {
    val data = List(
      (List(1,1), List(0,0), List(0,0))
      ,(List(100, 100), List(1,0), List(1,0))
      //,(List(4,8,12), List(0,1,0), List(1,5,3))
    )

    data.foreach { case (r, p, s) =>
      println(s"$r, $p, $s -> ${f(r, p, s, 0)}")
    }
  }

  def f(r: List[Int], p: List[Int], s: List[Int], i: Int): Int = {
    if (r.indices.exists(index => p(i % p.length) % r(index) != 0)) {
      1 + f(r, p.zip(s).map { case (pi, si) => pi + si }, s, 0)
    } else {
      0
    }
  }
}

```
> 0 votes

# Answer
# Haskell, 121 bytes

```
import Data.List
import Data.Ratio
z=zipWith.flip
t r p s=length$fst$break(null.tail.group.z(%)r)$iterate(z mod r.z(+)s)p

```

Try it online!

# Haskell, 135 bytes

```
import Data.List
import Data.Ratio
t r p s=length$fst$break(null.tail.group.zipWith(flip(%))r)$iterate(zipWith(flip mod)r.zipWith(+)s)p

```

Try it online!
> 0 votes

---
Tags: code-golf
---


title: The Möbius Function

text:
# Question
Title: The Möbius Function
The Möbius function is an important number theoretic function.

Your submission should accept a positive integer \\$n\\$ and return the value of the Möbius function evaluated at \\$n\\$.

### Definition

The Möbius function \\$μ(n)\\$ is defined as follows:

$$\mu(n) = \begin{cases} \hphantom{-}1, &n\text{ is squarefree and has an even number of distinct prime factors} \\ -1, &n\text{ squarefree and has an odd number of distinct prime factors} \\ \hphantom{-}0, &\text{otherwise} \end{cases}$$

\\$n\\$ is called *squarefree* if the exponents of the prime factorization of \\$n\\$ are all strictly less that two. (Alternatively: No prime to the power of two divides \\$n\\$).

### Test cases

Here you can see the first 50 values of μ:

Public Domain Image from Wikipedia

The Möbius function is sequence number A008683 in the OEIS.

These are the first 77 values:

```
1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, 0, 1, 1, -1, 0, 0, 1, 0, 0, -1, -1, -1, 0, 1, 1, 1, 0, -1, 1, 1, 0, -1, -1, -1, 0, 0, 1, -1, 0, 0, 0, 1, 0, -1, 0, 1, 0, 1, 1, -1, 0, -1, 1, 0, 0, 1, -1, -1, 0, 1, -1, -1, 0, -1, 1, 0, 0, 1

```

Larger values can also easily be checked in Wolframalpha.com or in the b-file of OEIS, as suggested by @MartinBüttner.

# Answer
> 15 votes
## Python 2, 48 bytes

```
m=lambda n,d=1:d%n and-m(d,n%d<1)+m(n,d+1)or 1/n

```

Earlier 51 byte version:

```
m=lambda n:1/n-sum(m(k)for k in range(1,n)if n%k<1)

```

Möbius-inverts the sequence `1,0,0,0,0...`.

The Möbius function has the property that for any `n>1`, the Möbius functions of `n`'s divisors sum to 0. So, for `n>1`, `μ(n)` is computed by negating the sum of `μ(k)` for all proper divisors `k` of `n`. For `n=1`, the output is `1`.

The code handles the base case by adding a floor-division `1/n`, which gives `1` for `n==1` and `0` otherwise.

Thanks to Dennis for saving 3 bytes with better recursive handling inspired by a similar structure in this challenge.

# Answer
> 13 votes
# Jelly, 7 bytes

Code:

```
ÆF>1’PS

```

Explanation:

```
ÆF       # This computes the prime factorization as well as the exponent
  >1     # Compares each element if it's greater than 1, resulting in 1's and 0's
    ’    # Decrement on each element
     P   # Compute the product
      S  # Compute the sum of the list

```

For example, the number **10**:

```
ÆF       # [[2, 1], [5, 1]]
  >1     # [[1, 0], [1, 0]]
    ’    # [[0, -1], [0, -1]]
     P   # [0, 1]
      S  # 1

```

And results in **1**.

Try it online.

# Answer
> 11 votes
## Mathematica, 9 bytes

```
MoebiusMu

```

Of course, Mathematica has a built-in. (And ~~will probably be~~ is beaten by Jelly anyway.)

# Answer
> 7 votes
## CJam, ~~18~~ 15 bytes

```
WrimFz~\1&+f/:*

```

The fact that CJam returns 1 in factorisation builtins for `n = 1` makes things a bit tricky.

Try it online | Test suite

Thanks to @PeterTaylor for the neat `1&+` trick for handling the 1 case.

## Explanation

```
W                 Push -1
 ri               Push input as int
   mF             Factorise input into [base exponent] pairs
     z~           Zip and unwrap pairs, leaving stack like [-1 bases exponents]
       \1&        Setwise intersect bases with 1, giving [1] for 1 and [] otherwise
          +       Append to exponent array
           f/     Divide the previously pushed -1 by each element in the array
                  This gives -1 for 1s and 0 otherwise, since / is int division
             :*   Take product

```

For `n > 1`, the modified array is just the exponents array. If `n` is squarefree then the array is all 1s, which become all -1s after division. Otherwise, if n has a prime square divisor, then there will be a 0 somewhere after division, giving a product of 0.

For `n = 1` the modified array is `[1] + [1]`, which becomes `[-1 -1]` after division, giving a product of 1.

---

Alternative 16:

```
rimF{1#2+3%(}%:*

```

This uses `#` (find) on each `[base exponent]` array to look for a 1, then maps `-1 -> 0, 0 -> 1, 1 -> -1`.

# Answer
> 6 votes
## Ruby, ~~65+7=72~~ 62+7=69 bytes

```
->x{((d=x.prime_division).all?{|_,n|n<2}?1:0)*(d.size%2*-2+1)}

```

+7 bytes for the `-rprime` flag.

We're doing this the very naïve way:

```
->x{
 (
  (d=x.prime_division)  # ex. input 20 results in [[2,2],[5,1]] here
  .all?{|_,n|n<2}?      # are all factors' exponents under 2?
  1:0                   # if so, result in a 1; otherwise, a 0
 )
 *                      # multiply that 1 or 0 by...
  (d.size%2*-2+1)       # magic
}

```

The "magic" part results in 1 if the number is even and -1 otherwise. Here's how:

```
Expression       Even  Odd
--------------------------
d.size%2         0     1
d.size%2*-2      0     -2
d.size%2*-2+1    1     -1

```

# Answer
> 6 votes
## Labyrinth, 87 bytes

```
1
:
}
?   @ "}){/{=:
""({! "      ;
} )   :}}:={%"
* _}}){     ;
{      #}):{{
")`%#/{+

```

Try it online!

### Short explanation

Here's a port of the algorithm used, in Python:

```
divisor = 1
mobius = 1
n = int(input())

while n != 1:
  divisor += 1
  count = 0

  while n % divisor == 0:
    n //= divisor
    count += 1

  mobius *= (count + 3)//(count + 1)%3*-1 + 1

print(mobius)

```

### Long explanation

The usual primer on Labyrinth:

* Labyrinth is stack-based and two-dimensional, with execution starting at the first recognised character. There are two stacks, a main stack and an auxiliary stack, but most operators only work on the main stack.
* At every branch of the labyrinth, the top of the stack is checked to determine where to go next. Negative is turn left, zero is straight ahead and positive is turn right.

Execution for this program starts at the top-left `1`.

```
Outer preparation
=================

1        Pop 0 (stack is bottomless and filled with 0s) and push 0*10+1 = 1
:}       Duplicate and shift to auxiliary stack
?        Read int from input
         Stack is now [div=1 n | mob=1]

Top of stack positive but can't turn right. Turn left into outer loop.

Begin outer loop
================
Inner preparation
-----------------

(        Decrement top of stack

If top was 1 (and is now zero), move forward and do...
------------------------------------------------------

{!       Print mob
@        Terminate

If top of stack was greater than 1, turn right and do...
--------------------------------------------------------

)        Increment n back to its previous value
_}       Push 0 and shift to aux
         This will count the number of times n can be divided by div
}){      Increment div
         Stack is now [div n | count mob]

Inner loop
----------

:}}      Dup n, shift both n's to aux
:=       Dup div and swap top of main with top of aux
{%       Shift div down and take mod
         Stack is now [div n%div | n count mob]

If n%div == 0, move forward and do...
-----------------------------------

;        Pop n%div
:={/     Turn n into n/div
{)}      Increment count
         (continue inner loop)

If n%div != 0, turn right (breaking out of inner loop) and do...
================================================================

;        Pop n%div
{{       Pull n and count from aux
:)}      Dup and increment count, giving (count+1), and shift to aux
#+       Add length of stack to count, giving (count+3)
{/       Calculate (count+3)/(count+1)
#%       Mod by length of stack, giving (count+3)/(count+1)%3
`        Multiply by -1
)        Increment, giving (count+3)/(count+1)%3*-1 + 1
         This is 1 if count was 0, -1 if count was 1 and 0 if count > 1
{*}      Multiply mob by this number
         (continue outer loop)

```

# Answer
> 5 votes
# 05AB1E, 8 bytes

Code:

```
.p0K1›<P

```

Explanation:

```
.p        # Get the prime factorization exponents
  0K      # Remove all zeroes from the list
    1›    # Compare each element if greater than 1
      <   # Decrement on each element
       P  # Take the product

```

Uses the CP-1252 encoding

# Answer
> 5 votes
## Pyth, 9 bytes

```
^_{IPQlPQ

```

Explanation:

```
^_{IPQlPQ    Implicit: Q=input
    PQ       Prime factorization of Q
  {I         Is invariant under uniquify.
  {IPQ       1 if Q is squarefree; 0 otherwise.
 _{IPQ       -1 if Q is squarefree; 0 otherwise.
^     lPQ    Exponentiation to length of PQ.

```

Try it here.

# Answer
> 5 votes
# Java 8, ~~72~~ ~~68~~ ~~65~~ 64 bytes

```
n->{int r=1,i=1;for(;i++<n;)r=n%i<1?(n/=i)%i<1?0:-r:r;return r;}

```

-4 bytes thanks to *@PeterTaylor*.

Port of @Meerkat's .NET C# answer, which I first golfed a bit further, so make sure to upvote him!

Try it online.

**Explanation:**

```
n->{                // Method with integer as both parameter and return-type
  int r=1,          //  Result-integer, starting at 1
  i=1;for(;i++<n;)  //  Loop `i` in the range [1, n]:
    r=n%i<1?        //   If `n` is divisible by `i`:
       (n/=i)       //    Divide `n` by `i` first
        %i<1?       //    And if `n` is still divisible by `i`:
         0          //     Change `r` to 0
        :           //    Else:
         -r         //     Swap the sign of `r` (positive to negative or vice-versa)
      :             //    Else:
       r;           //     Leave `r` unchanged
  return r;}        //  Return `r` as result

```

# Answer
> 4 votes
## CJam, 20 bytes

```
rimf1-___&=\,2%!2*(*

```

Run it against a range of inputs here.

Seems golfable.

# Answer
> 4 votes
# R ~~39~~16 bytes

```
numbers::moebius

```

Requires you having the numbers package installed on your system...

Edit: Far simpler if I read the specs appropriately \[thanks @AlexA.\]

# Answer
> 4 votes
# Factor \+ `math.extras`, 6 bytes

```
mobius

```

Attempt This Online!

# Answer
> 3 votes
# Pyth, 16 Bytes

```
?nl{PQlPQZ^_1lPQ

```

Try it online!

My first actual Pyth answer. Suggestions appreciated! :)

## Explanation

My solution uses the fact that a number is squarefree, if its prime-factors contain no number more than once. If the input is squarefree, the Möbius-Function takes the value -1^(number of primefactors).

```

?n        if not equal
  l{PQ      length of the list of the distinct input-Primefactors
  lPQ       length of the list of primefactors including duplicates
    Z         Input is not squarefree, so output Zero
  ^_1lPQ  if input is squarefree, output -1^(number of prime-factors)

```

# Answer
> 3 votes
# MATL, 15 ~~17~~ bytes

```
tq?YftdAwn-1w^*

```

This uses current release (10.1.0) of the language/compiler.

**Try it online!**

### Explanation

```
t         % implicit input. Duplicate that
q         % decrement by 1. Gives truthy (nonzero) if input exceeds 1
?         % if input exceeds 1, compute function. Otherwise leave 1 on the stack
  Yf      % vector of prime factors. Results are sorted and possibly repeated
  td      % duplicate and compute differences
  A       % true if all differences are nonzero
  w       % swap
  n       % number of elements in vector of prime factors, "x"
  -1w^    % -1^x: gives -1 if x odd, 1 if x even
  *       % multiply by previously obtained true/false value, so non-square-free gives 0
          % implicitly end "if"
          % implicitly display stack contents

```

# Answer
> 3 votes
# C# (.NET Core), 86 73 72 65 bytes

```
a=>{int b=1,i=1;for(;++i<=a;)b=a%i<1?(a/=i)%i<1?0:-b:b;return b;}

```

Try it online!

*-13 bytes: streamlined loops, added return variable (thanks to Kevin Cruijssen)*
*-1 byte: changed setting b to zero to a ternary from an if (thanks to Kevin Cruijssen)*
*-7 bytes: changed if statement in for loop to a ternary (thanks to Peter Taylor and Kevin Cruijssen)*

Ungolfed:

```
a => {
    int b = 1, i = 1;           // initialize b and i to 1

    for(; ++i <= a;)            // loop from 2 (first prime) to a
        b = a % i < 1 ?                     // ternary: if a is divisible by i
            ((a /= i) % i < 1 ? 0 : -b) :   // if true: set b to 0 if a is divisible by i squared, otherwise flip sign of b
            b;                              // if false: don't change b

    return b;                   // return b (positive for even numbers of primes, negative for odd, zero for squares)
}

```

# Answer
> 2 votes
# Pyth, 11

```
*{IPQ^_1lPQ

```

Test suite

This multiplies the boolean value of if the prime factors are squarefree by `-1` to the power of the number of prime factors that the number has.

`I` is an invariance check on the preceeding operator, which here is `{`, which is the unique-ify operator.

# Answer
> 2 votes
# Japt, 21 bytes

```
V=Uk)¬¥Vâ ¬?Vl v ªJ:0

```

Test it online!

# Answer
> 2 votes
## Seriously, ~~19~~ 18 bytes

```
,w;`iX1=`Mπ)l1&τD*

```

Try it online!

Explanation:

```
,w;`iXDY`Mπ)l1&τD*
,w;                push two copies of the full prime factorization of the input
                      (a list of [base, exponent] pairs)
   `    `M         map the following function:
    iX1=             flatten list, discard, equal to 1
                        (push 1 if exponent == 1 else 0)
          π)       product of list, push to bottom of stack
            1&     push 1 if the # of prime factors is even else 0
              τD   double and decrement (transform [0,1] to [-1,1])
                *  multiply

```

# Answer
> 2 votes
# Julia, 66 bytes

```
n->(f=factor(n);any([values(f)...].>1)?0:length(keys(f))%2>0?-1:1)

```

This is a lambda function that accepts an integer and returns an integer. To call it, assign it to a variable.

Ungolfed:

```
function µ(n::Int)
    # Get the prime factorization of n as a Dict with keys as primes
    # and values as exponents
    f = factor(n)

    # Return 0 for non-squarefree, otherwise check the length of the list
    # of primes
    any([values(f)...] .> 1) ? 0 : length(keys(f)) % 2 > 0 ? -1 : 1
end

```

# Answer
> 2 votes
# PARI/GP, 7 bytes

```
moebius

```

Sadly `möbius` is not available. :)

# Answer
> 2 votes
# Julia, 35 bytes

```
\(n,k=1)=k%n>0?n\-~k-k\0^(n%k):1÷n

```

Based on @xnor's Python answer. Try it online!

# Answer
> 2 votes
# Seriously, 11 bytes

Golfing suggestions welcome. Try it online!

```
;y;l0~ⁿ)π=*

```

**Ungolfing**

```
     Implicit input n.
;    Duplicate n.
y    Push a list of the distinct prime factors of n. Call it dpf.
;    Duplicate dpf.
l    Push len(dpf).
0~   Push -1.
ⁿ    Push (-1)**len(dpf).
)    Rotate (-1)**len(dpf) to BOS. Stack: dpf, n, (-1)**len(dpf)
π    Push product(dpf).
=    Check if product(dpf) == n.
      This is only true if n is squarefree.
*    Multiply (n is squarefree) by (-1)**len(dpf).
     Implicit return.

```

# Answer
> 1 votes
# GNU sed, 89 bytes

```
#!/bin/sed -rf
s/.*/factor &/e
s/.*://
/\b([0-9]+) \1\b/!{
s/[0-9]+//g
s/$/1/
s/  //g
y/ /-/
}
s/ .*/0/

```

# Answer
> 1 votes
# J, 18 bytes

```
[:*/3<:@|2+2<._&q:

```

# Answer
> 1 votes
## Microsoft Office Excel, British version, 196 bytes

```
=IF(ROW()>=COLUMN(),IF(AND(ROW()=1,COLUMN()=1),1,IF(COLUMN()=1,
-SUM(INDIRECT(ADDRESS(ROW(),2)&":"&ADDRESS(ROW(),ROW()))),
IF(MOD(ROW(),COLUMN())=0,INDIRECT(ADDRESS(FLOOR(ROW()/COLUMN(),1),
1)),""))),"")

```

Excel cell formula to be entered in cells A1 to AX50.

# Answer
> 1 votes
## Javascript (ES6), 48 bytes

```
f=(n,i=1)=>n-1?n%++i?f(n,i):(n/=i)%i?-f(n,i):0:1

```

First of all - this is my first code golf post so I may misunderstand the rules to some extent. In this submission the last character `;` could be omitted and it'll still work but I'm not even sure if the code would be valid according to the ES6 specs. Anyways, a short explanation.

First, I'll explain the idea a bit; we take `n`, and we try dividing it by the integer `i`. If it's divisible, then we do so and we check if it's divisible by `i` again. If that's the case, then we need to return `0`. Otherwise, we can try another `i`. The cool thing is, we can just start at `i=2` and just add increase it by `1` every time, so that we divide out all the prime factors.

So, the code works like this:

```
f=(n,i=1)=>                                           We will increase i by one at the start of
                                                         the function body, so default is 1
           n-1?                                       Check if n==1.
               n%++i?                                 If i isn't, increase i by 1, check if n
                                                         is divisible by i
                     f(n,i):                          if it isn't, we check the next i
                            (n/=i)%i?                 if it is, divide n by i, and check for
                                                         divisibility by i again
                                     -f(n,i):         if it not, then we flip the value to
                                                         account for the 1 and -1 depending on the
                                                         amount of factors
                                             0:       if it's divisible by i twice, done.
                                               1      if we're at 1, divided out all factors,
                                                         then we return 1. The line with
                                                         -f(n,i) will then take care of the sign

```

So, that's my submission.

# Answer
> 1 votes
# Haskell, 96 bytes

```
import Data.Numbers.Primes
import Data.List
m=(\f->last$0:[(-1)^length f|f==nub f]).primeFactors

```

Try it online!

# Answer
> 0 votes
# Vyxal, 47 bitsv1, 5.875 bytes

```
ǐÞu$†Ǎ*

```

Try it Online!

What do you mean it's not morbin' time? I love vyncode and how just re-arranging things makes the program shorter.

## Explained

```
ǐÞu$†Ǎ*
ǐ       # prime factors of input with duplicates
 Þu     # all unique?
   $†Ǎ  # -1 ** len(prime_factors(input))
      * # multiply

```

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


title: Implement the Quine-McCluskey algorithm

text:
# Question
Title: Implement the Quine-McCluskey algorithm
The Quine-McCluskey algorithm merges disjunctors in a disjunction like $$ \lnot x\_0 \land \lnot x\_1 \land \lnot x\_2 \land \lnot x\_3 \lor\\ x\_0 \land \lnot x\_1 \land x\_2 \land \lnot x\_3 \lor\\ \lnot x\_0 \land x\_1 \land x\_2 \land \lnot x\_3 \lor\\ \lnot x\_0 \land \lnot x\_1 \land \lnot x\_2 \land x\_3 \lor\\ \lnot x\_0 \land x\_1 \land \lnot x\_2 \land x\_3 \lor\\ x\_0 \land x\_1 \land \lnot x\_2 \land x\_3 \lor\\ \lnot x\_0 \land x\_1 \land x\_2 \land x\_3 \lor\\ x\_0 \land x\_1 \land x\_2 \land x\_3 $$ into fewer disjunctors in an equivalent disjunction: $$ x\_1 \land x\_3 \lor\\ \lnot x\_0 \land \lnot x\_1 \land \lnot x\_2 \lor\\ \lnot x\_0 \land x\_1 \land x\_2 \lor\\ x\_0 \land \lnot x\_1 \land \lnot x\_2 \land x\_3 $$ by merging like this: $$x\_0\land x\_1\lor\lnot x\_0\land x\_1 \iff (x\_0\lor\lnot x\_0)\land x\_1\iff x\_1$$.

https://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/code/qmc/ will generate test cases to taste.

## Your task

Your task is to write a function transforming any disjunction into an equivalent disjunction of minimal disjunctor count.

The QMC algorithm imperative in the headline is a sloppy summary and a mere recommendation, no hard requirement.

You can encode the data any way fit, that is $$\lnot x\_1 \land \lnot x\_2 \land x\_3$$ can become

* \[3,0,0,1\]
* \[(1,0),(2,0),(3,1)\]
* (14,8)
*

This is `code-golf`. Shortest code wins.

# Answer
# Kamilalisp, 139 bytes

```
(defun s m \let-seq(def a \⍸ \= 1 \⌼ $(foldl1 +)@/= m m)(↩ (= 0 \⍴ a) m)(def p m$[⍎ a])\^⍪ p \⍠ m \[tie@* ⍎ $(foldl1 =)] p)

```

"Ungolfed":

```
(⍥← s m \○⊢¨
  (○← a \⍸ \= 1 \⌼ $(⌿⊙← +)∘≠ m m)   ; Find all possible rows we can join.
  (↩ (= 0 \⍴ a) m)                    ; If we can't join anything, yield.
  (○← p m$[⍎ a])                      ; Determine the contents of the rows in the matrix to be joined.
  \^⍪ p \⍠ m \[⌿⊙⍧∘* ⍎ $(⌿⊙← =)] p) ; Adjoin the new row, remove the merged two.

```

In essence, the algorithm finds two rows in the matrix that represents the expression (where every cell, either -1, 1, or 0 represents that the boolean literal is either negated, taken as given, or not used), that differ at most by one entry. Then, if no such rows are found, the algorithm returns the original matrix. If at least one such pair exists, it is removed from the matrix, the difference between is computed as a mask (e.g. for -1 -1 1 1 and -1 -1 1 -1, the mask is 1 1 1 0), which is then multiplied by the first (or equivalently second) element of the pair to form a new entry in the expression matrix.

Some test cases, etc:

Attempt This Online!
> 3 votes

# Answer
# Haskell, 340 bytes

```
import Data.Bits;import Data.List;import Data.List.Ordered
o d[]=d;o _ s=s
p(a:b:c)|a==b=a|0<1=p(b:c)
q(_,b)(c,d)=c.&.b==c.&.d
r t s=and[or[q f e|e<-s]|f<-t]
s(a,b)(c,d)=[(a.&.complement x,b.&.d)|a==c,let x=xor b d,1==popCount x]
t d=nubSort$concatMap(\c->o[c]$concatMap(s c)d)d
u d=head$sortOn length$filter(r d)$subsequences$p$iterate t d

```

Here a disjunctor is represented by `(significantbitmask,setbits)` fiddled by `q` and `s`. `s` combines two disjunctors if they have the same `significantbitmask` and differ in exactly one bit. `o[c]` prevents disjunctors from disappearing if they combine with nobody. `u` computes a minimal disjunction: `t` merges antivalents in `d` until `p` no more merges occur, then it filters for `r` sufficient subsets as the merges can produce superfluous disjunctors.

Try it online!
> -3 votes

---
Tags: code-golf, logic
---


# Question
Title: Create a kind of quine, such that the program prints one character of itself, then two, then three and so on
Create quine variant such that the program prints its first character, then the first two, then three and so on until the whole program is printed.

## Example

Suppose your code is `@@@@@2` in some language. Then the output should be

```
@
@@
@@@
@@@@
@@@@@
@@@@@2

```

in that order, each line separated by a newline.

The winner is the shortest quine like this.

# Answer
# Jelly, 10 bytes

```
“;⁾vṾÄY”vṾ

```

Try it online!

### How it works

```
“;⁾vṾÄY”vṾ  Main link. No arguments.

“;⁾vṾÄY”    Set the return value to the string ';⁾vṾÄY'.
         Ṿ  Uneval; yield a string representation of the string, i.e., '“;⁾vṾÄY”'.
        v   Dyadic eval; execute the string to the left, passing the string to the
            right as argument.
  ⁾vṾ         Literal; yield 'vṾ'.
 ;            Concatenate the argument ('“;⁾vṾÄY”') and 'vṾ', yielding '“;⁾vṾÄY”vṾ'.
     Ä        Accumulate; take the cumulative sum.
              Since string addition is concatenation in Python (and Jelly doesn't do
              type checks), this yields all prefixes of the string.
      Y       Join the prefixes, separated by linefeeds.

```
> 5 votes

# Answer
# Husk, 18 bytes

```
G:""S+s"G:\"\"S+s"

```

Try it online!

## Explanation

An extension of the standard quine `S+s"S+s"`. To get all the prefixes we cannot use  (`heads`), because `ḣS+s"ḣS+s"` would `show "ḣS+s"` which results in `"\7715S+s"`:

```
ḣS+s"ḣS+s"

```

Try it online!

So we need to re-implement `heads` without using any unicode, this can be done by `scanl snoc ""` (`snoc` is just a flippped version of `(:)`), ie. `G:""` which is ASCII.
> 3 votes

# Answer
# Oracle SQL, 154 bytes

```
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;

```

Test in SQL Plus

```
SQL> set lines 160 pages 0
SQL> select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;
s
se
sel
sele
selec
select
select
select s
select su
select sub
select subs
select subst
select substr
select substr(
select substr(r
select substr(rp
select substr(rpa
select substr(rpad
select substr(rpad(
select substr(rpad(1
select substr(rpad(1,
select substr(rpad(1,2
select substr(rpad(1,24
select substr(rpad(1,240
select substr(rpad(1,240,
select substr(rpad(1,240,'
select substr(rpad(1,240,'|
select substr(rpad(1,240,'||
select substr(rpad(1,240,'||c
select substr(rpad(1,240,'||ch
select substr(rpad(1,240,'||chr
select substr(rpad(1,240,'||chr(
select substr(rpad(1,240,'||chr(3
select substr(rpad(1,240,'||chr(39
select substr(rpad(1,240,'||chr(39)
select substr(rpad(1,240,'||chr(39))
select substr(rpad(1,240,'||chr(39)),
select substr(rpad(1,240,'||chr(39)),5
select substr(rpad(1,240,'||chr(39)),53
select substr(rpad(1,240,'||chr(39)),53,
select substr(rpad(1,240,'||chr(39)),53,l
select substr(rpad(1,240,'||chr(39)),53,le
select substr(rpad(1,240,'||chr(39)),53,lev
select substr(rpad(1,240,'||chr(39)),53,leve
select substr(rpad(1,240,'||chr(39)),53,level
select substr(rpad(1,240,'||chr(39)),53,level)
select substr(rpad(1,240,'||chr(39)),53,level)f
select substr(rpad(1,240,'||chr(39)),53,level)fr
select substr(rpad(1,240,'||chr(39)),53,level)fro
select substr(rpad(1,240,'||chr(39)),53,level)from
select substr(rpad(1,240,'||chr(39)),53,level)from
select substr(rpad(1,240,'||chr(39)),53,level)from d
select substr(rpad(1,240,'||chr(39)),53,level)from du
select substr(rpad(1,240,'||chr(39)),53,level)from dua
select substr(rpad(1,240,'||chr(39)),53,level)from dual
select substr(rpad(1,240,'||chr(39)),53,level)from dual
select substr(rpad(1,240,'||chr(39)),53,level)from dual c
select substr(rpad(1,240,'||chr(39)),53,level)from dual co
select substr(rpad(1,240,'||chr(39)),53,level)from dual con
select substr(rpad(1,240,'||chr(39)),53,level)from dual conn
select substr(rpad(1,240,'||chr(39)),53,level)from dual conne
select substr(rpad(1,240,'||chr(39)),53,level)from dual connec
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect b
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by l
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by le
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by lev
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by leve
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<1
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<15
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;s
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;se
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;sel
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;sele
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;selec
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select s
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select su
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select sub
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select subs
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select subst
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(r
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rp
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpa
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,2
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,24
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'|
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||c
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||ch
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(3
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39))
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),5
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,l
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,le
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,lev
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,leve
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)f
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)fr
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)fro
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from d
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from du
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dua
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual c
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual co
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual con
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual conn
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual conne
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connec
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect b
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by l
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by le
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by lev
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by leve
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<1
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<15
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155
select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;select substr(rpad(1,240,'||chr(39)),53,level)from dual connect by level<155;

154 rows selected.

```
> 3 votes

# Answer
# Haskell, ~~100~~ 98 bytes

<sup>-2 bytes thanks to Dennis</sup>

```
main=mapM g[1..98];g n=putStrLn$take n$id<>show$"main=mapM g[1..98];g n=putStrLn$take n$id<>show$"

```

Try it online!

Surprisingly ~~2~~ 4 bytes shorter than the obvious port of my Husk answer:

`main=mapM putStrLn$scanl((.pure).(++))[]$id<>show$"main=mapM putStrLn$scanl((.pure).(++))[]$id<>show$"`
> 3 votes

# Answer
# Python 3.8 (pre-release), 54 bytes

```
exec(a:="s=''\nfor i in'exec(a:=%r)'%a:print(s:=s+i)")

```

Try it online!

I also have 2 variants of the same length :

```
exec(a:="s=''\nfor i in'exec(a:=%r)'%a:s+=i;print(s)")

```

```
exec(a:="s='';[print(s:=s+i)for i in'exec(a:=%r)'%a]")

```

## How it works :

It is the standard "exec" quine in python: `exec(a:="print('exec(a:=%r)'%a)")` in which I added an iteration. This base quine is pretty usefull because it doesn't require to write all the added byte twice unlike the shorter `a='a=%r;print(a%%a)';print(a%a)` quine
> 3 votes

# Answer
# JavaScript, 47 bytes

This can probably be improved.

## Revisions

20 bytes have been saved so far between 3 versions!

### Revision 5

There's been a lot of bytes saved with this revision:

* Don't assign a single-use variable for the quine to save 2 bytes
* Use templated strings for the quine to save a byte
* Use a single parameter (`_`) instead of no parameters (`()`) to save a byte

These three changes get it down to 47 bytes!!

```
(s=_=>{for(c of `(s=${s})()`)alert(name+=c)})()

```

### Revision 4

On most pages, it seems that `window.name` is an empty string by default. We can take advantage of this to get 53 bytes!

```
(s=()=>{q="(s="+s+")()";for(c of q)alert(name+=c)})()

```

Unfortunately this is not the case for the snippet page, but try running it with the developer tools!

### Revision 3

We can save 2 bytes, down to 55 bytes, by combining the two statements in the loop into one:

```
(s=()=>{q="(s="+s+")()",h="";for(c of q)alert(h+=c)})()
```

### Revision 2

We can get down to 57 bytes by using an EcmaScript 2015 arrow function:

```
(s=()=>{q="(s="+s+")()",h="";for(c of q)h+=c,alert(h)})()
```

### Revision 1

We can also get down to 61 bytes by using `alert` instead of `console.log`, if you consider that to be printing:

```
(function s(){q="("+s+")()",h="";for(c of q)h+=c,alert(h)})()
```

### Initial Version

Initially, this script was at 67 bytes:

```
(function s(){q="("+s+")()",h="";for(c of q)h+=c,console.log(h)})()
```

## Explanation

Here's the prettified code:

```
(function func() {
  quine = "(" + func + ")();";
  substr = "";
  for (char of quine) {
    substr += char;
    console.log(substr);
  }
})();
```

We start with a standard quine, then we define `substr`. We loop over each character of the quine, add it to `substr`, then output that.
> 2 votes

# Answer
# Excel, 182 bytes

```
=LEFT(SUBSTITUTE("=LEFT(SUBSTITUTE(@,CHAR(64),CHAR(34)&@&CHAR(34)),ROW(1:182))",CHAR(64),CHAR(34)&"=LEFT(SUBSTITUTE(@,CHAR(64),CHAR(34)&@&CHAR(34)),ROW(1:182))"&CHAR(34)),ROW(1:182))

```

Added `LEFT( ~ , ROW(1:182))` to standard quine.

## Cheesy version, 32 bytes

```
=LEFT(FORMULATEXT(A1),ROW(1:32))

```
> 2 votes

# Answer
# Vyxal `Dj`, 40 bits, 5 bytes

```
`I¦`I¦

```

Try it Online!

## Explained

```
`I¦`I¦
     ¦   # Prefixes of
`I¦`     # the string "I¦"
    I    # with `I¦` prepended
# joined on newlines by the j flag

```
> 2 votes

# Answer
# Befunge-98 (PyFunge), 31 bytes

```
"2+,a<_@#-2$,k-'p11+1:g11+4+ff

```

Try it online!

Modification of a wrapping string literal quine that repeats printing prefixes until it prints everything.

### Explanation:

```
"         Wrapping string literal that pushes the code backwards
 2+,      Add 2 to the space and print as "
   ,a<    Reverse direction and print a newline
"         Push the code again, but the right way this time
                          +4+ff   Push a quote
                       g11        Get the counter at (1,1)
                                  This is initially 32 (space)
                 p11+1:    Increment and store back at (1,1)
              -'          Subtract 31 from the counter
            ,k             Print counter many times plus one
          2$    Swap and check if the next number on the stack is 2
 2     _@#      If so, end the program as this is the leftover 2
   ,a           Print a newline and repeat

```
> 1 votes

# Answer
# Jelly, 14 bytes

```
“Ṿ;¹¹ƤY”Ṿ;¹¹ƤY

```

Try it online!
> 1 votes

# Answer
# 05AB1E, 17 bytes

```
0"D34çýη»"D34çýη»

```

Try it online!
> 1 votes

# Answer
# PowerShell Core, 44 bytes

```
&($f={&{1..44|%{"&(`$f={$f})"|% s*g 0 $_}}})

```

Try it online!

Idea borrowed from this answer by bb216b3acfd8f72cbc8f899d4d6963, thank you!
> 1 votes

# Answer
# Japt `-R`, 11 bytes

```
BõîQi"BõîQi

```

Test it

```
BõîQi"BõîQi
B               :11
 õ              :Range [1,B]
  î             :For each mould the following
   Q            :  Quotation mark
    i           :  Prepend
     "BõîQi     :    String literal
                :Implicit output joined with newlines

```
> 1 votes

# Answer
# Thunno 2 `N`, 12 bytes

```
"DṘs+ƒ"DṘs+ƒ

```

#### Explanation

```
"DṘs+ƒ"DṘs+ƒ  # Full program
"DṘs+ƒ"       # Push the string "DṘs+ƒ"
       D      # Duplicate it
        Ṙ     # Get its representation
              # (surround by quotes)
         s+   # Prepend this to the string
           ƒ  # Get the new string's prefixes
              # Implicit output, joined by newlines

```

#### Screenshot

(click to enlarge)
> 1 votes

# Answer
# Julia 0.6, 91 bytes

```
Q="1:91.|>x->println(\"Q=\$(repr(Q));\$Q\"[1:x])";1:91.|>x->println("Q=$(repr(Q));$Q"[1:x])

```

Try it online!

Adapted from the Julia quine from Rosetta Code, which is based on `repr`

Requires at least Julia 0.6, but includes syntax that is deprecated in 0.7 and removed in 1.0

There exist shorter quines in Julia (32 and 35-byte quines based on `@show`, 37-byte quine based on `eval`), and it might be possible to adapt either of these methods.
> 1 votes

# Answer
# Python 2, 72 bytes

```
s,f="",'s,f="",%r\nfor i in f%%f:s+=i;print s'
for i in f%f:s+=i;print s

```

Try it online!
> 0 votes

# Answer
# Pyth, 17 bytes

```
j._jN*2]"j._jN*2]

```

Try it online!
> 0 votes

# Answer
# Japt `-R`, 11 bytes

```
CÇîQi"CÇîQi

```

Try it online!

If the leading newline isn't acceptable, here's a ~~15~~ 13-byte alternative:

```
Dõ_îQi"Dõ_îQi

```

Try it online!
> 0 votes

# Answer
# Pushy, ~~28~~ ~~26~~ 24 bytes

```
`I"Ov:L69w69`96w96L:vO"I

```

**Try it online!**

## Explanation:

```
`I"Ov:L69w79`                \ String literal: push this to stack
             96              \ Append backtick: I"Ov:L69w69`
               w             \ Mirror:          I"Ov:L69w69`96w96L:vO"I
                96           \ Append backtick: I"Ov:L69w69`96w96L:vO"I`
                             \ We now have the source code, backwards, on the main stack.

                  L:         \ len(stack) times do:
                    v        \     Move last character to auxiliary stack
                     O"I     \     Print the auxiliary stack

```
> 0 votes

# Answer
# Java 10, 202 bytes

```
v->{var s="v->{var s=%c%s%1$c;s=s.format(s,34,s);for(int i=0;++i<s.length();)System.out.println(s.substring(0,i));}";s=s.format(s,34,s);for(int i=0;++i<s.length();)System.out.println(s.substring(0,i));}

```

Try it online.

**Explanation:**

part of the explanation:

* `var s` contains the unformatted source code.
* `%s` is used to input this String into itself with `s.format(...)`.
* `%c`, `%1$c`, and the `34` are used to format the double quotes
* `s.format(s,34,s)` puts it all together

Challenge part of the explanation:

* `for(int i=0;++i<s.length();)` then loops `i` in the range \[1, formatted\_code\_length)
* `System.out.println(...)` prints the String with trailing newlines
* `s.substring(0,i)` gets the substring of the formatted code in the character-range `[0,i)`.
> 0 votes

# Answer
# Julia, 63 bytes

```
(a=:([println(("(a=:($(a)))|>eval")[1:x]) for x = 1:63]))|>eval

```

Try it online!

The spaces and parenthesis are necessary because the code is stored in an `Expr` (AST), which will add them when interpolated.

based on this quine:
`(a=:(print("(a=:($(a)))|>eval")))|>eval` Try it online!
> 0 votes

---
Tags: code-golf, quine
---