title: A twist of a trivial sequence

text:
# Question
Title: A twist of a trivial sequence
## Introduction

Consider a sequence of integers \\$f\\$ defined as follows:

1. \\$f(2) = 2\\$
2. If \\$n\\$ is an odd prime, then \\$f(n) = \frac{f(n-1) + f(n+1)}2\\$
3. If \\$n = p\cdot q\\$ is composite, then \\$f(n) = f(p)\cdot f(q)\\$

It's not very hard to see that \\$f(n) = n\\$ for every \\$n \ge 2\\$, and thus computing \\$f\\$ wouldn't be a very interesting challenge. Let's make a twist to the definition: halve the first case and double the second case. We get a new sequence \\$g\\$ defined as follows:

1. \\$g(2) = 1\\$
2. If \\$n\\$ is an odd prime, then \\$g(n) = g(n-1) + g(n+1)\\$
3. If \\$n = p\cdot q\\$ is composite, then \\$g(n) = g(p)\cdot g(q)\\$

## The task

Your task is to take an integer \\$n \ge 2\\$ as input, and produce \\$g(n)\\$ as output. You don't have to worry about integer overflow, but you should be able to compute \\$g(1025) = 81\\$ correctly, and your algorithm should theoretically work for arbitrarily large inputs.

You can write a full program or a function. The lowest byte count wins.

## Example

I claimed above that \\$g(1025) = 81\\$, so let's compute it by hand. The prime factorization of **1025** gives

```
1025 = 5*5*41 => g(1025) = g(5)*g(5)*g(41)

```

Since **41** is prime, we get

```
g(41) = g(40) + g(42)

```

Next, we compute the prime factorizations of **40** and **42**:

```
40 = 2*2*2*5 => g(40) = g(2)*g(2)*g(2)*g(5) = g(5)
42 = 2*3*7 => g(42) = g(2)*g(3)*g(7) = g(3)*g(7)

```

For these small primes we get

```
g(3) = g(2) + g(4) = 1 + 1 = 2
g(5) = g(4) + g(6) = 1 + 2 = 3
g(7) = g(6) + g(8) = 2 + 1 = 3

```

This means that

```
g(41) = g(40) + g(42) = g(5) + g(3)*g(7) = 3 + 2*3 = 9

```

and

```
g(1025) = g(5)*g(5)*g(41) = 3*3*9 = 81

```

## Test cases

Here are the values of \\$g\\$ up to **50**.

```
2 -> 1
3 -> 2
4 -> 1
5 -> 3
6 -> 2
7 -> 3
8 -> 1
9 -> 4
10 -> 3
11 -> 5
12 -> 2
13 -> 5
14 -> 3
15 -> 6
16 -> 1
17 -> 5
18 -> 4
19 -> 7
20 -> 3
21 -> 6
22 -> 5
23 -> 7
24 -> 2
25 -> 9
26 -> 5
27 -> 8
28 -> 3
29 -> 9
30 -> 6
31 -> 7
32 -> 1
33 -> 10
34 -> 5
35 -> 9
36 -> 4
37 -> 11
38 -> 7
39 -> 10
40 -> 3
41 -> 9
42 -> 6
43 -> 11
44 -> 5
45 -> 12
46 -> 7
47 -> 9
48 -> 2
49 -> 9
50 -> 9

```

# Answer
> 7 votes
## Haskell, 69 bytes

```
x#a|x<3=1|a>x=a#2+(x-1)#2|mod x a<1,a<x=a#2*div x a#2|b<-a+1=x#b
(#2)

```

Usage example: `(#2) 1025` -\> `81`

The parameter `a` is counted up until it divides `x` or it reaches `x` (i.e. `x` is prime). It it one byte shorter to test for `a > x` and add a further condition (`a < x`) to the modulus test instead of testing for `a == x`, because the former binds `a` to `x+1`, which helps in the recursive call. Compare:

```
|a==x=(x+1)#2+(x-1)#2|mod x a<1=
|a>x=a#2+(x-1)#2|mod x a<1,a<x=

```

# Answer
> 4 votes
# Jelly, 18 bytes

```
‘;’Ñ€Sµ1n2$?
ÆfÇ€P

```

Try it online!

This is basically just a direct translation of the specification. (After thinking about it a bit, I suspect that if there is a closed formula for finding the sequence, it'd be more bytes than the direct approach.)

## Explanation

We have two mutually recursive functions. Here's the helper function (which calculates **g(n)** for prime **n**):

```
‘;’Ñ€Sµ1n2$?
           ?  If
        n2$     the input is not equal to 2 (parsed as a group due to $)
      µ       then do all the following (parsed as a group due to µ):
‘;’             Find the list [n+1, n-1];
   Ñ€           Call the main program on each element (i.e. [g(n+1),g(n-1)]);
     S          and return the sum of the list (i.e. g(n+1)+g(n-1)).
              Otherwise:
       1        Return 1.

```

And here's the main program, which calculates **g(n)** for any **n**:

```
ÆfÇ€P
Æf            Factorize the input into its prime factors;
  Ç€          Call the helper function on each element of that list;
    P         Then take the product.

```

Clearly, if we call the main program on a prime number, everything's a no-op except the `Ç`, so it returns **g(n)** in this case. The rest of the program handles the behaviour for composite **n**.

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

```
f=(n,d=2)=>n-2?d<n?n%d?f(n,d+1):f(n/d)*f(d):f(n-1)+f(n+1):1

```

### Test

```
f=(n,d=2)=>n-2?d<n?n%d?f(n,d+1):f(n/d)*f(d):f(n-1)+f(n+1):1

// f(2) to f(50)
for(N = 2, list = []; N <= 50; N++) {
  list.push(N + ' -> ' + f(N));
}
console.log(list.join(', '));

// f(1025)
console.log(f(1025));
```

# Answer
> 4 votes
# Jelly, 13 bytes

```
Æfḟ2µ‘,’ß€€SP

```

Try it online!

### How it works

```
Æfḟ2µ‘,’ß€€SP  Main link. Argument: n

Æf             Yield the array of prime factors of n.
  ḟ2           Remove all occurrences of 2.
    µ          Begin a new, monadic chain. Argument: A (array of odd prime factors)
     ‘         Increment all elements of A.
       ’       Decrement all elements of A.
      ,        Pair; yield [A+1, A-1].
        ß€€    Map the main link over all elements of A+1 and A-1.
           S   Column-wise reduce by addition.
            P  Reduce by multiplication.

```

# Answer
> 3 votes
# Python 2, 85 69 bytes

```
g=lambda n,k=3:(n&~-n<1)or n%k and g(n,k+2)or(g(k+1)+g(k-1))*g(n/k,k)

```

# Answer
> 3 votes
# Clojure, 126 bytes

```
(defn t[n](if(= n 2)1(let[a(+(.indexOf(for[b(range 2 n)](mod n b)2)0))](if(> a 1)(*(t(/ n a))(t a))(+(t(dec n))(t(inc n)))))))

```

Yay! It's almost twice as long as the Python answer!

Ungolfed and an explanation:

```
(defn trivial [n]
  ; Define the function.
  (if (= n 2) 1
  ; If the number is 2, return 1
    (let [a (+ 2 (.indexOf (for [b (range 2 n)] (mod n b)) 0))]
      ; Let a be the lowest prime factor of n
      (if (> a 1)
        ; The .indexOf function returns -1 if a is a prime, so -1 + 2 = 1.
        ; Checks if a is a prime.
        (* (trivial (/ n a)) (trivial a))
        ; If a is prime, return the trivial(a/n) * trivial(a).
        (+ (trivial (dec n)) (trivial (inc n)))))))
        ; Else, return trivial(n-1) + trivial(n + 1).

```

# Answer
> 2 votes
# Mathematica, 83 bytes

```
Which[#<4,#-1,PrimeQ@#,Tr[#0/@({#-1,#+1}/2)],0<1,1##&@@#0/@Divisors@#~Part~{2,-2}]&

```

Unnamed recursive function of one positive integer argument, returning an integer. Not all that short, in the end. `Tr[#0/@({#-1,#+1}/2)]` (in the case where the input is prime) calls the function on both members of the ordered pair `{(#-1)/2,(#+1)/2}` and adds the results; this is fine since the function has the same value at `(#-1)/2` and `#-1`, for example. Similarly, `1##&@@#0/@Divisors@#~Part~{2,-2}` calls the function on the second-smallest divisor `#` and its complememtary divisor (the second-larget divisor) and multiplies the answers together.

# Answer
> 2 votes
# Python 2, 62 bytes

```
f=lambda n,k=3:k>n or n%k and f(n,k+2)or(f(k-1)+f(k+1))*f(n/k)

```

Try it online!

# Answer
> 2 votes
## Clojure, 120 bytes

```
(defn g[n](if(= n 2)1(if-let[F(first(for[i(range 2 n):when(=(mod n i)0)]i))](*(g F)(g(/ n F)))(+(g(dec n))(g(inc n))))))

```

Uses `:when` to get divisors of `n`, `F` is `nil` if no such divisor is found (`n` is prime).

# Answer
> 1 votes
# , 89 bytes

```
g=function(n)"if"(n<3,1,"if"(sum(y<-!n%%2:n)<2,g(n-1)+g(n+1),g(k<-1+which(y)[1])*g(n/k)))

```

Try it online!

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


title: One-zero dividend

text:
# Question
Title: One-zero dividend
## Challenge description

For every positive integer `n` there exists a number having the form of `111...10...000` that is divisible by `n` i.e. a decimal number that starts with all `1`'s and ends with all `0`'s. This is very easy to prove: if we take a set of `n+1` different numbers in the form of `111...111` (all `1`'s), then at least two of them will give the same remainder after division by `n` (as per pigeonhole principle). The difference of these two numbers will be divisible by `n` and will have the desired form. Your aim is to write a program that finds this number.

## Input description

A positive integer.

## Output description

A number `p` in the form of `111...10...000`, such that `p ≡ 0 (mod n)`. If you find more than one - display any of them (doesn't need to be the smallest one).

## Notes

Your program has to give the answer in a reasonable amount of time. Which means brute-forcing is not permited:

```
p = 0
while (p != 11..10.00 and p % n != 0)
    p++

```

Neither is this:

```
do
    p = random_int()
while (p != 11..10.00 and p % n != 0)

```

Iterating through the numbers in the form of `11..10..00` is allowed.

Your program doesn't need to handle an arbitrarily large input - the upper bound is whatever your language's upper bound is.

## Sample outputs

```
2: 10
3: 1110
12: 11100
49: 1111111111111111111111111111111111111111110
102: 1111111111111111111111111111111111111111111111110

```

# Answer
## Mathematica, 29 bytes

```
⌊10^(9EulerPhi@#)/9⌋10^#&

```

Code by Martin Büttner.

On input \\$n\\$, this outputs the number with \\$9\varphi(n)\\$ ones followed by \\$n\\$ zeroes, where \\$\varphi(\cdot)\\$ is the Euler totient function. With a function `phi`, this could be expressed in Python as

```
lambda n:'1'*9*phi(n)+'0'*n

```

It would suffice to use the factorial \\$n!\\$ instead of \\$\varphi(n)\\$, but printing that many ones does not have a reasonable run-time.

*Claim:* \\$9\varphi(n)\\$ ones followed by \\$n\\$ zeroes is a multiple of \\$n\\$.

*Proof:* First, let's prove this for the case that \\$n\\$ is not a multiple of \\$2, 3, \text{or } 5\\$. We'll show the number with consisting of \\$\varphi(n)\\$ ones is a multiple of \\$n\\$.

The number made of \\$k\\$ ones equals \\$\frac{10^k-1}9\\$. Since \\$n\\$ is not a multiple of \\$3\\$, this is a multiple of \\$n\\$ as long as \\$10^k-1\\$ is a factor of \\$n\\$, or equivalently if \\$10^k \equiv 1\mod n\\$. Note that this formulation makes apparent that if \\$k\\$ works for the number of ones, then so does any multiple of \\$k\\$.

So, we're looking for \\$k\\$ to be a multiple of the order of \\$k\\$ in the multiplicative group modulo n. By Lagrange's Theorem, any such order is a divisor of the size of the group. Since the elements of the group are the number from \\$1\\$ to \\$n\\$ that are relatively prime to \\$n\\$, its size is the Euler totient function \\$\varphi(n)\\$. So, we've shown that \\$10^{\varphi(n)} \equiv 1 \mod n\\$, and so the number made of \\$\varphi(n)\\$ ones is a multiple of \\$n\\$.

Now, let's handle potential factors of \\$3\\$ in \\$n\\$. We know that \\$10^{\varphi(n)}-1\\$ is a multiple of \\$n\\$, but \\$\frac{10^{\varphi(n)}-1}9\\$ might not be. But, \\$\frac{10^{9\varphi(n)}-1}9\\$ is a multiple of \\$9\\$ because it consists of \\$9\varphi(n)\\$ ones, so the sum of its digits a multiple of \\$9\\$. And we've noted that multiplying the exponent \\$k\\$ by a constant preserves the divisibility.

Now, if \\$n\\$ has factors of \\$2\\$'s and \\$5\\$'s, we need to add zeroes to end of the output. It way more than suffices to use \\$n\\$ zeroes (in fact \\$\log\_2(n)\\$ would do). So, if our input \\$n\\$ is split as \\$n = 2^a \times 5^b \times m\\$, it suffices to have \\$9\varphi(m)\\$ ones to be a multiple of \\$n\\$, multiplied by \\$10^n\\$ to be a multiple of \\$2^a \times 5^b\\$. And, since \\$n\\$ is a multiple of \\$m\\$, it suffices to use \\$9\varphi(n)\\$ ones. So, it works to have \\$9\varphi(n)\\$ ones followed by \\$n\\$ zeroes.
> 25 votes

# Answer
## Python 2, 44 bytes

```
f=lambda n,j=1:j/9*j*(j/9*j%n<1)or f(n,j*10)

```

When `j` is a power of 10 such as 1000, the floor-division `j/9` gives a number made of 1's like 111. So, `j/9*j` gives 1's followed by an equal number of 0's like 111000.

The function recursively tests numbers of this form, trying higher and higher powers of 10 until we find one that's a multiple of the desired number.
> 10 votes

# Answer
# Pyth, 11 bytes

```
.W%HQsjZ`TT

```

Test suite

Basically, it just puts a 1 in front and a 0 in back over and over again until the number is divisible by the input.

Explanation:

```
.W%HQsjZ`TT
                Implicit: Q = eval(input()), T = 10
.W              while loop:
  %HQ           while the current value mod Q is not zero
      jZ`T      Join the string "10" with the current value as the separator.
     s          Convert that to an integer.
          T     Starting value 10.

```
> 6 votes

# Answer
# Haskell, 51 bytes

```
\k->[b|a<-[1..],b<-[div(10^a)9*10^a],b`mod`k<1]!!0

```

Using xnor’s approach. nimi saved a byte!
> 5 votes

# Answer
## CJam, ~~28~~ ~~25~~ 19 bytes

*Saved 6 bytes with xnor's observation that we only need to look at numbers of the form `1<sup>n</sup>0<sup>n</sup>`.*

```
ri:X,:)Asfe*{iX%!}=

```

Test it here.

### Explanation

```
ri:X    e# Read input, convert to integer, store in X.
,:)     e# Get range [1 ... X].
As      e# Push "10".
fe*     e# For each N in the range, repeat the characters in "10" that many times,
        e# so we get ["10" "1100" "111000" ...].
{iX%!}= e# Select the first element from the list which is divided by X.

```
> 4 votes

# Answer
# JavaScript (ES6), 65 bytes

**Edit** 2 bytes saved thx @Neil

It works within the limits of javascript numeric type, with 17 significant digits. (So quite limited)

```
a=>{for(n='';!(m=n+=1)[17];)for(;!(m+=0)[17];)if(!(m%a))return+m}

```

**Less golfed**

```
function (a) {
    for (n = ''; !(m = n += '1')[17]; )
        for (; !(m += '0')[17]; )
            if (!(m % a))
                 return +m;
}

```
> 4 votes

# Answer
# Husk, ~~11~~ 10 bytes

<sup>*-1 byte thanks to Razetime!*</sup>

```
ḟ¦⁰modṘḋ2N

```

Try it online! Constructs the infinite list `[10,1100,111000,...]` and selects the first element which is a multiple of the argument.
> 4 votes

# Answer
# Mathematica, ~~140~~ 55 bytes

```
NestWhile["1"<>#<>"0"&,"1",FromDigits@#~Mod~x>0&/.x->#]

```

Many bytes removed thanks to xnor's 1^n0^n trick.

**Minimal value, ~~140~~ 156 bytes** This gives the smallest possible solution.

```
NestWhile["1"<>#&,ToString[10^(Length@NestWhileList[If[EvenQ@#,If[10~Mod~#>0,#/2,#/10],#/5]&,#,Divisors@#~ContainsAny~{2, 5}&],FromDigits@#~Mod~m>0&/.m->#]&

```

It calculates how many zeros are required then checks all possible `1` counts until it works. It can output a number with no 0 but that can be fixed by adding a `<>"0"` right before the final `&`.
> 3 votes

# Answer
## Haskell, 37 bytes

```
f n=[d|d<-"10",i<-[1..n*9],gcd n i<2]

```

This uses the fact that it works to have `9*phi(n)` ones, where `phi` is the Euler totient function. Here, it's implemented using `gcd` and filtering, producing one digit for each value `i` that's relatively prime to it that is in the range `1` and `9*n`. It also suffices to use this many zeroes.
> 3 votes

# Answer
# Perl 5, 26 bytes

includes a byte for `-n` (`-M5.01` is free)

```
($.="1$.0")%$_?redo:say$.

```

## Explanation

`$.` starts off with value 1. We immediately concatenate it with 1 beforehand and 0 afterward, yielding 110, and reassign that to `$.` — that's what the `$.="1$.0"` does.

The assignment returns the assigned value so when we take it modulo the input number `$_` we obtain 0 (false) if 110 is divisible by the input and nonzero (true) otherwise.

* In the latter case, we `redo`, i.e. repeat the block (the `-n` switch makes the whole thing a loop block, and incidentally, assigns `$_` to the input number). This concatenates another 1 and 0, yielding 11100, etc.
* If 110, or 11100, or 1111000, or whatever we're up to, is divisible by the input, we stop and `say` (print) it.

Note that every number divides such a number (i.e. that has one more 1 than the numbers of 0s it has). After all, if it divides something with more 1s than 0s, you can append 0s and it'll still divide that. And if divides something with fewer 1s than 0s, say *m* 1s and *n* 0s with *m* \< *n*, then it also divides the number with 2*m* 1s and *n* 0s.
> 3 votes

# Answer
# Jelly, 11 bytes

```
⁵DxⱮḅ⁵ḍ@Ƈ⁸Ḣ

```

Try it online!

Ignoring runtime requirements, we can reduce this to 10 bytes using xnor's method, but with \\$\varphi(n)\\$ replaced with \\$n!\\$:

```
!,µ⁵Dx"µFḌ

```

Try it online!

## How they work

```

⁵DxⱮḅ⁵ḍ@Ƈ⁸Ḣ - Main link. Takes n on the left
⁵D          - Yield [1, 0]
   Ɱ        - For each integer i in [1, 2, ..., n]:
  x         -   Repeat each element of [1, 0] i times
    ḅ⁵      - Convert each back into an integer
        Ƈ   - Keep those for which the following is true:
      ḍ@    -   Is divisible by
         ⁸  -   n
          Ḣ - Take the first value of those remaining

```

```

!,µ⁵Dx"µFḌ - Main link. Takes n on the left
!          - Yield n!
 ,         - Yield [n!, n]. Call this l
  µ        - Begin new link with l on the left
   ⁵D      - Yield [1, 0]
      "    - Zip [1, 0] with [n!, n] and do the following over each pair:
     x     -   Repeat
           - This yields [[1, 1, ..., 1], [0, 0, ..., 0]].
             The first element has n! 1s and the second n 0s
             Call this k
       µ   - Begin new link with k on the left
        F  - Flatten k
         Ḍ - Convert to integer

```
> 3 votes

# Answer
## Sage, 33 bytes

```
lambda n:'1'*9*euler_phi(n)+'0'*n

```

This uses xnor's method to produce the output.

Try it online
> 2 votes

# Answer
# 05AB1E, 8 bytes

```
$Õ9*×Î×«

```

Port of *@xnor*'s Mathematica answer, so make sure to upvote him!!

Try it online or verify all test cases.

**Explanation:**

```
$         # Push 1 and the input-integer
 Õ        # Pop the input, and get Euler's totient of this integer
  9*      # Multiply it by 9
    ×     # Repeat the 1 that many times as string
     Î    # Push 0 and the input-integer
      ×   # Repeat the 0 the input amount of times as string
       «  # Concatenate the strings of 1s and 0s together
          # (after which the result is output implicitly)

```

---

A more to-the-point iterative approach would be **11 bytes**:

```
TS∞δ×øJ.ΔIÖ

```

Try it online or verify all test cases.

**Explanation:**

```
T             # Push 10
 S            # Convert it to a list of digits: [1,0]
  ∞           # Push an infinite positive list: [1,2,3,...]
   δ          # Apply double-vectorized on these two lists:
    ×         #  Repeat the 1 or 0 that many times as string
              # (we now have a pair of infinite lists: [[1,11,111,...],[0,00,000,...]])
      ø       # Zip/transpose; swapping rows/columns:
              #  [[1,0],[11,00],[111,000],...]
       J      # Join each inner pair together:
              #  [10,1100,111000,...]
        .Δ    # Find the first value in this list which is truthy for:
          IÖ  #  Check that it's divisible by the input-integer
              # (after which the result is output implicitly)

```
> 2 votes

# Answer
# bc, 58 bytes

```
define f(n){for(x=1;m=10^x/9*10^x;++x)if(m%n==0)return m;}

```

## Sample results

```
200: 111000
201: 111111111111111111111111111111111000000000000000000000000000000000
202: 11110000
203: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000
204: 111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000
205: 1111100000
206: 11111111111111111111111111111111110000000000000000000000000000000000
207: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
208: 111111000000
209: 111111111111111111000000000000000000
210: 111111000000
211: 111111111111111111111111111111000000000000000000000000000000
212: 11111111111110000000000000
213: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
214: 1111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000
215: 111111111111111111111000000000000000000000
216: 111111111111111111111111111000000000000000000000000000
217: 111111111111111111111111111111000000000000000000000000000000
218: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
219: 111111111111111111111111000000000000000000000000

```
> 1 votes

# Answer
# dc, 27 bytes

```
Odsm[O*lmdO*sm+O*dln%0<f]sf

```

This defines a function `f` that expects its argument in the variable `n`. To use it as a program, `?sn lfx p` to read from stdin, call the function, and print the result to stdout. Variable `m` and top of stack must be reset to 10 (by repeating `Odsm`) before `f` can be re-used.

## Results:

```
200: 111000
201: 111111111111111111111111111111111000000000000000000000000000000000
202: 11110000
203: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000
204: 111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000
205: 1111100000
206: 11111111111111111111111111111111110000000000000000000000000000000000
207: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
208: 111111000000
209: 111111111111111111000000000000000000
210: 111111000000
211: 111111111111111111111111111111000000000000000000000000000000
212: 11111111111110000000000000
213: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
214: 1111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000
215: 111111111111111111111000000000000000000000
216: 111111111111111111111111111000000000000000000000000000
217: 111111111111111111111111111111000000000000000000000000000000
218: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
219: 111111111111111111111111000000000000000000000000

```
> 1 votes

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


title: Sum power of digits

text:
# Question
Title: Sum power of digits
# Challenge :

Given two non-negative integers `(X and Y > 1)` calculate the sum of digits of their powers . i.e : sum of digits of `X ^ Y` .

---

# Input :

Two non-negative integers `X` and `Y`

---

# Output :

The sum of digits of X raised to power Y `X ^ Y`.

# Examples :

```
5 , 2                    ---> 7
9 , 4                    ---> 18
3 , 17                   ---> 27

```

Both numbers will be greater than 1

---

# Restrictions :

This is so shortest code (in bytes) for each language wins.

---

# Notes :

All input will be valid. i.e : Both inputs will be greater than 1 and will be integers.

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

```
(x,y)->sumdigits(x^y)

```

Try it online!

# Answer
> 2 votes
# Jelly, 3 bytes

Jelly trivialises this task

```
*DS

```

A dyadic link accepting a positive integer, X, on the left and a positive integer, Y, on the right which returns the resulting positive integer.

**Try it online!**

### How?

```
*DS - Link: X, Y
*   - exponentiate X to the Y
 D  - to a list of its digits
  S - sum

```

# Answer
> 2 votes
# C, ~~60~~ 56 Bytes

This is my first time golfing, and I think this code can be shortened. Feel free to help and improve this. Edit: Does not work when you give it a and b such that a^b is over 2^31.

4 Bytes saved thanks to Dennis.

```
i,q;f(a,b){for(i=0,q=pow(a,b);q;q/=10)i+=q%10;return i;}

```

test it by editing the numbers in the printf

# Answer
> 1 votes
# Python 3, 34 bytes

```
lambda a,b:sum(map(int,str(a**b)))

```

Try it online!

# Answer
> 1 votes
# APL+WIN, 8 bytes

Prompts for y followed by x:

```
+/⍎¨⍕⎕*⎕

```

# Answer
> 1 votes
# , 12 bytes 11 bytes

-1 byte thanks to Cows quack

```
1#.,.&.":@^

```

Try it online!

`^` power

`,.&.":` convert to list of digits

`1#.` add up the digits

# Answer
> 1 votes
# Haskell, ~~29~~ 28 bytes

```
x%y=sum[read[d]|d<-show$x^y]

```

Try it online!

-1 byte thanks to user9549915

# Answer
> 1 votes
# Neim, 2 bytes

```

```

Power ; implicitly coerce to list; sum

Try it online!

# Answer
> 1 votes
# Funky, 31 bytes

```
a=>b=>{n=0fors in''..a^b n-=-s}

```

Try it online!

# Answer
> 1 votes
# Charcoal, 6 bytes

```
ＩΣＩＸＮＮ

```

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

```
    Ｎ   First input as a number
     Ｎ  Second input as a number
   Ｘ    Power
  Ｉ     Cast to string
 Σ      Sum of digits
Ｉ       Cast to string
        Implicitly print

```

# Answer
> 1 votes
# Japt, 5 bytes

Saved 1 byte thanks to @Shagy

```
pV ìx

```

Try it online!

# Answer
> 0 votes
# JavaScript (Node.js), ~~37~~ 32 bytes

-5 bytes thanks to @Shaggy.

```
X=>Y=>eval([...''+X**Y].join`+`)

```

Try it online!

# Explanation :

```
X =>                      // First input X
    Y =>                  // second input Y
        eval(             // evaluate
            [...''+       // convert what is next to string and map to array
            X**Y].        // X raised to power Y
                join`+`   // join them into a string with a plus sign between each
        )                 // The whole thing gets evaluated using `eval`

```

---

# Answer
> 0 votes
# Pyth, 6 bytes

```
ssM`^F

```

Try it online!

If the list input isn't allowed, you can just replace the `F` with `E` and it'll take in two integers (one on each line) but do the operation in reverse order from input order.

# Answer
> 0 votes
# Ruby, 24 bytes

```
->x,y{(x**y).digits.sum}

```

Try it online!

# Answer
> 0 votes
# JavaScript (Node.js), 36 bytes

```
X=>g=(Y,d=X**Y)=>d&&d%10+g(Y,d/10|0)

```

Try it online!

# Answer
> 0 votes
# Perl 6, 16 bytes

```
(* ***).comb.sum

```

Try it online!

# Answer
> 0 votes
# Gol\>\<\>, 11 bytes

```
XWaSD}|lR+B

```

Try it online!

A function that accepts X and Y on the stack and leaves the result as the only value on the stack.

### Example full program & How it works

```
1AGIE;IGN
XWaSD}|lR+B

1AG          Register row 1 as function G
   IE;       Take input X as int; halt if EOF
      I      Take input Y as int
       GN    Call G with stack [X Y] and print the result as int
             Repeat indefinitely

X            n = X**Y
 W    |      While top is nonzero...
  aSD          Pop n, push n / 10 and n % 10
     }         Move the remainder to the bottom
             Now the stack contains the digits
       lR+   Sum everything
          B  Return

```

# Answer
> 0 votes
# Stax, 4 bytes

```
║▼δ&

```

Run and debug it

Unpacked:

```
|*E|+

```

Run and debug this one

Explanation:

```
|*E|+ Full program, implicit input
      Stack: 5 2
|*    Power
      Stack: 25
  E   Decimal digits
      Stack: [ 2, 5 ]
   |+ Sum array
      Stack: 7
      Implicit output

```

# Answer
> 0 votes
## PHP, 44 Bytes

No loop, passing both arguments to the script. Try it Online

**Code**

```
<?=array_sum(str_split($argv[0]**$argv[1]));

```

This just takes both arguments calculates `X to the power of Y`, explodes the string into an array and adds each digit

# Answer
> 0 votes
# Husk, 3 bytes

```
Σd^

```

Try it online! Takes `Y` followed by `X`.

---
Tags: code-golf, math
---


title: The Knight's Dialer

text:
# Question
Title: The Knight's Dialer
Imagine you place a knight chess piece on a phone dial pad. This chess piece moves from keys to keys in an uppercase "L" shape: two steps horizontally followed by one vertically, or one step horizontally then two vertically:

```
 +-+
 |1|   2    3
 +-+
    `-------v
     |     +-+
  4  | 5   |6|
     |     +-+
     |
     |+-+
  7  >|8|   9
      +-+

       0

```

Suppose you dial keys on the keypad using only hops a knight can make. Every time the knight lands on a key, we dial that key and make another hop. The starting position counts as hop 0.

How many distinct numbers can you dial in N hops from a particular starting position?

# Example

**Starting key**: 6
**Number of hops**: 2

**Numbers that can be formed**:

```
6 0 6
6 0 4
6 1 6
6 1 8
6 7 2
6 7 6

```

So six different numbers can be formed from the key 6 and with 2 hops.

# Constraints

**Input:** You will receive two numbers as input. You can mix those input and use any format you wish. The starting key will be a number between 0 and 9, the number of hops will be a nonnegative integer with no upper limit.

**Output:** You will output a single number in any format you want.

# Test cases

```
(key,hops)   result

(6,0)         1
(6,1)         3
(6,2)         6
(6,10)        4608
(6,20)        18136064
(5,0)         1
(5,1)         0

```

# Scoring

This is code golf. To encourage participation in the future, no answer will be accepted.

# Note

This is strongly inspired by *The Knight's Dialer*, a former Google interview question. But be careful, it's not identical, so don't simply base your answer on the code you see there.

# Answer
> 20 votes
# JavaScript (ES6),  ~~62 61~~  60 bytes

My Python port, ported back to JS. :-p

```
f=(n,k,o=k%2)=>n--?k-5&&(2-o)*f(n,!k*3-~o)+(k&5&&f(n,o*4)):1

```

Try it online!

Below is my original 62-byte version, which is easier to understand:

```
f=(n,k)=>n--?k&1?k-5&&f(n,2)+f(n,4):2*f(n,k?1:4)+(k&4&&f(n)):1

```

Try it online!

### How?

There are 4 groups of keys which are really connected together. All keys within a group have the exact same behavior.

* Corners `1`, `3`, `7`, `9` (in green). Characterization: odd keys that are not equal to \\$5\\$.
* Left/right sides `4`, `6` (in blue). Characterization: even keys for which we have \\$k \operatorname{and}4 = 4\\$.
* Top/bottom sides `2`, `8` (in yellow). Characterization: non-zero even keys for which we have \\$k \operatorname{and}4 = 0\\$.
* The `0` key (in red).

The `5` key is secluded and processed separately.

The figure on the right is a weighted directed graph showing which target groups can be reached from a given source group, and how many distinct keys are valid targets within each target group.

This algorithm does one recursive call per target group from the current group, multiplies each result by the corresponding weight and sums them all.

Only the first iteration is expecting \\$k\in\[0..9\]\\$. For the next ones, we just set \\$k\\$ to the leading key of each group (\\$1\\$, \\$4\\$, \\$2\\$ and \\$0\\$ respectively).

---

# JavaScript (ES6),  ~~86 74~~  72 bytes

```
f=(p,n,k=10)=>n?k--&&(306>>(p*2149^k*2149)%71%35&1&&f(k,n-1))+f(p,n,k):1

```

Try it online!

### 71 bytes

Much, much slower.

```
f=(p,n,k=10)=>n?k--&&(306>>(p*2149^k*2149)%71%35&1)*f(k,n-1)+f(p,n,k):1

```

Try it online!

### Finding a hash function

We are looking for a function \\$h(p,k)\\$ telling whether \\$p\\$ and \\$k\\$ are connected by a knight hop. Because this function is commutative and because the result is always the same when \\$p=k\\$, a bitwise XOR looks like a good candidate.

We can't directly do \\$p \operatorname{XOR} k\\$ because, for instance, \\$0 \operatorname{XOR} 4\\$ and \\$3 \operatorname{XOR} 7\\$ are both equal to \\$4\\$ although \\$(0,4)\\$ are connected and \\$(3,7)\\$ are not.

We need to get more entropy by applying some multiplier \\$M\\$ such that \\$(M\times p)\operatorname{XOR}\\:(M\times k)\\$ is collision-free. The first few valid multipliers are \\$75\\$, \\$77\\$, \\$83\\$, ... (We *could* apply two distinct multipliers to \\$p\\$ and \\$k\\$, but we would lose the benefit of the function being commutative. So it's unlikely to lead to a smaller expression.)

For each valid multiplier, we then look for some modulo chain to reduce the size of the lookup table.

By running a brute-force search with \\$M\<10000\\$ and two modulos \\$1\<m\_0\<m\_1\<100\\$ followed by a modulo \\$32\\$, the following expression arises:

> $$h(p,k)=((((p\times 2149)\operatorname{XOR}\\:(k\times 2149))\bmod 71)\bmod 35)\bmod 32$$

We have a valid hop iff \\$h(p,k)\in\\{1,4,5,8\\}\\$, which can be represented as the small bit-mask \\$100110010\_2=306\_{10}\\$.

Hence the JS implementation:

```
306 >> (p * 2149 ^ k * 2149) % 71 % 35 & 1

```

Note that the final modulo \\$32\\$ is implicitly provided by the right-shift.

### Commented

```
f = (                       // f is a recursive function taking:
  p,                        //   p = current position
  n,                        //   n = number of remaining hops
  k = 10                    //   k = key counter
) =>                        //
  n ?                       // if n is not equal to 0:
    k-- && (                //   decrement k; if it was not 0:
      306 >>                //     right-shifted lookup bit-mask
      (p * 2149 ^ k * 2149) //     apply the XOR
      % 71 % 35             //     apply the modulo chain
      & 1 &&                //     if the least significant bit is set:
        f(k, n - 1)         //       do a recursive call with p = k and n - 1
    ) +                     //
    f(p, n, k)              //     add the result of a recursive call
                            //     with the updated k
  :                         // else:
    1                       //   stop the recursion
                            //   and increment the final result

```

# Answer
> 8 votes
# Python 2, 68 bytes

*Saved 1 byte thanks to @Sisyphus*
*Saved 5 more bytes thanks to @xnor*

This is based on the logic used in my 62-byte JS version, with a different implementation to make it easier to golf in Python. I've since ported this back to JS, as it turned out to be shorter as well.

```
f=lambda n,k:n<1or k-5and(2-k%2)*f(n-1,4-k%-9%2)+9%~k%2*f(n-1,k%2*2)

```

Try it online!

Below is a summary of the results returned by each expression, split by key groups:

```
 expression | 1 3 7 9 | 2 8 | 4 6 | 0 | description
------------+---------+-----+-----+---+---------------------------------------
 2-k%2      | 1 1 1 1 | 2 2 | 2 2 | 2 | weight for the 1st recursive call
 4-k%-9%2   | 4 4 4 4 | 3 3 | 3 3 | 4 | target key for the 1st recursive call
 9%~k%2     | 1 1 1 1 | 1 1 | 0 0 | 0 | weight for the 2nd recursive call
 k%2*2      | 2 2 2 2 | 0 0 | - - | - | target key for the 2nd recursive call

```

# Answer
> 5 votes
# Jelly,  ~~29~~  28 bytes

```
⁵ṗ’;;Ṣe“¡¿Ṅ\ȷḳ€°ị’Ds2¤ʋƝPɗ€S

```

A dyadic Link accepting the number of hops on the left and the key on the right which yields the number of paths.

**Try it online!**

### How?

Forms all length `hops` decimal numbers, prepends `key` to each and counts how many have all valid neighbours by lookup in a compressed list. (Note: when `hops` is zero the fact that the empty product is one means the Link yields 1, as desired.)

---

### Here is another 28

```
⁵ṗ’µ;⁴+3!PƝ%⁽W⁶%31fƑ“¤®€×‘)S

```

This one uses some funky arithmetic to decide whether each move is valid by adding three to each of the two digits, taking their factorials, multiplying these together, getting the remainder after division by \\$22885\\$, getting the remainder after division by \\$31\\$, and checking if the result is one of \\$\\{3,8,12,17\\}\\$.

# Answer
> 5 votes
# Python 2, 83 bytes

```
f=lambda s,n:n<1or sum(f(i,n-1)for i in range(10)if`i`+`s`in`0x20cb0e9fd6fe45133e`)

```

Try it online!

A recursive solution. Checks for pairs of digits that are a knight's move away by them being consecutive in the hardcoded string `604927618343816729406`, written one byte shorter in hex. This string is a palindrome because the adjacency relationship being symmetric, but I didn't see a shorter way to take advantage of that and remove the redundancy.

**83 bytes**

```
f=lambda s,n:n<1or sum(f(i,n-1)for i in range(10)if 6030408>>(s*353^i*353)%62%29&1)

```

Try it online!

**85 bytes**

```
def f(s,n):a=b=c=d=1;exec"a,b=b+c,2*a;c,d=b+d,2*c;"*n;print[d,a,b,a,c,n<1,c,a,b,a][s]

```

Try it online!

A different idea giving a fast, iterative solution. We take advantage of the knight-move adjacency graph of the phone keypad being symmetric:

```
3--8--1
|     |
4--0--6
|     |
9--2--7

```

Note that 0 doesn't break the top-bottom symmetry of the keypad because it connects just to 4 and 6 on the centerline. The number 5 is isn't drawn; it doesn't connect to anything.

We use the symmetry to collapse down to four types of locations:

```
a--b--a
|     |
c--d--c
|     |
a--b--a

a: 1379
b: 28
c: 46
d: 5

```

We now have the transitions (some appearing multiple times):

```
a -> b, c
b -> a, a
c -> a, a, d
d -> c, c

```

This corresponds to the update of counts at each step of `a,b,c,d=b+c,2*a,2*a+d,2*c`. This can be written shorter as `a,b=b+c,2*a;c,d=b+d,2*c`, as pointed out by ovs saving 2 bytes.

So, we iterate `n` steps to produce the correspond values of `a,b,c,d`, and now we need to select the one corresponding to the start digit `s`. We need a mapping of each digit `0-9` to the corresponding entry `a,b,c,d`, with `5` going to `n<0`. The code just uses a direct array selector: `[d,a,b,a,c,n<1,c,a,b,a][s]`.

There's probably a shorter way using the symmetry that `s` and `10-s` are in the same category, and so we can do something like `s*s%10` to collapse these, or even `s*s%10%8` to get a distinct fingerprint for each type. With optimizations, this method might take the lead.

# Answer
> 4 votes
# Charcoal, 31 bytes

```
ＦＮ≔⭆η§⪪”)‴↘Ｓ‴Ｐeυ!&q]3⁰4”¶ＩκηＩＬη

```

Try it online! Link is to verbose version of code. Takes the number of hops as the first input. Too slow for large numbers of hops. Explanation:

```
ＦＮ

```

Input the number of hops and repeat that many times.

```
≔⭆η§⪪”)‴↘Ｓ‴Ｐeυ!&q]3⁰4”¶Ｉκη

```

Map over every character in the string and list its possible next hops. Example: `6``170``682646``1701379170390170` → ...

```
ＩＬη

```

Count the total number of hops found.

Faster 44-byte version:

```
≔Ｅχ⁼ιＩηηＦＮ≔Ｅ⪪”)∧↑mG@⁰EBü)‽₂≕↖”χΣＥκ×Ｉμ§ηνηΣＩη

```

Try it online! Link is to verbose version of code. Explanation: Works by repeatedly multiplying a next hop transition matrix.

# Answer
> 4 votes
# Perl 5, (`-p`) 63 bytes

```
eval's/./(46,68,79,48,390,"",170,26,13,24)[$&]/ge;'x<>;$_=y///c

```

Try it online!

# Answer
> 4 votes
# Python 3, 88 bytes

```
f=lambda s,n:n<1or sum(map(f,'46740 021268983 1634    9 7'[int(s)::10].strip(),[n-1]*3))

```

Try it online!

-15 bytes thanks to ovs

-2 bytes thanks to Jonathan Allan

# Answer
> 4 votes
# K (ngn/k), ~~60~~ ~~53~~ ~~52~~ 49 bytes

```
#,//(4 6;6 8;7 9;4 8;0 3 9;!0;0 1 7;2 6;1 3;2 4)/

```

Try it online!

Takes input as two separate arguments; `hops` as the first, `keys` as the second.

Uses a list to map keys to each other key a "hop" away. When combined with `/`, this functions as a finite-state machine, seeded with `key` and run for `hops` iterations. `,//` flattens the result into a one dimensional array and `#` takes its count.

# Answer
> 3 votes
# Wolfram Language, 108 bytes

```
Tr@MatrixPower[AdjacencyMatrix[4~KnightTourGraph~3~VertexDelete~{10,12}],#2,SparseArray[Mod[#,10,1]->1,10]]&

```

Try it online!

You know, there's probably a shorter solution for this, but I enjoy the mathematics of this one. This gets the adjacency matrix for the graph, raises it to the power of the number of jumps, and multiplies it by a vector representing which key it starts from. The elements of the resulting vector give the number of paths to each key, so the total gives the total number of paths of a given length.

# Answer
> 2 votes
# 05AB1E, ~~24~~ 22 bytes

```
F•žNjεEÿ¶^²è+%•5¡sèS}g

```

Amount of hops as first input, and the starting digit as second input.

Try it online or verify all test cases (except for the one with 20 hops, which times out).

**Explanation:**

```
F               # Loop the first (implicit) input amount of times:
 •žNjεEÿ¶^²è+%• #  Push compressed integer 46568579548530955107526513524
   5¡           #  Split it on 5: [46,68,79,48,309,"",107,26,13,24]
     s          #  Swap to take the current list of digits,
                #  or the second (implicit) input in the first iteration
      è         #  (0-based) index those into this list
       S        #  Convert it to a flattened list of digits
                #  ("" becomes an empty list [])
}g              # After the loop: pop the list of digits, and take its length
                # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (sections *How to compress large integers?*) to understand why `•žNjεEÿ¶^²è+%•` is `46568579548530955107526513524`.

# Answer
> 2 votes
# Java 8, ~~137~~ ~~129~~ ~~91~~ 89 bytes

```
int f(int n,int k){return--n<0?1:k%2>0?k==5?0:f(n,2)+f(n,4):2*f(n,k>0?1:4)+k/4%2*f(n,0);}

```

Port of *@Arnauld*'s JavaScript answer, provided by *@OlivierGrégoire*.
-2 byte thanks to *@ceilingcat*.

Try it online.

**Old ~~137~~ 129 bytes answer:**

```
(s,h)->{for(;h-->0;){var t="";for(var c:s.getBytes())t+="46,68,79,48,309,,107,26,13,24".split(",")[c-48];s=t;}return s.length();}

```

Starting digit as a String input, amount of hops as an integer.

Try it online.

**Explanation:**

```
(s,h)->{                    // Method with String & integer parameter & integer return
  for(;h-->0;){             //  Loop the integer amount of times:
    var t="";               //   Temp-String, starting empty
    for(var c:s.getBytes()) //   Inner loop over the digit-codepoint of the String:
      t+=                   //    Append to the temp-String:
         "46,68,79,48,309,,107,26,13,24".split(",")[c-48]);
                            //     The keys the current digit can knight-jump to
    s=t;}                   //   After the inner loop, replace `s` with the temp-String
  return s.length();}       //  Return the length of the String as result

```

# Answer
> 2 votes
# T-SQL, 197 bytes

Returns null for no solutions

This can handle 25 hops in 10 seconds

```
WITH C as(SELECT 0i,1*translate(@n,'37986','11124')x,1q
UNION ALL
SELECT-~i,y,q*(2+1/~(y*~-a))FROM(values(1,4),(1,2),(4,0),(2,1),(4,1),(0,4))x(a,y),c
WHERE a=x AND i<@)
SELECT
sum(q)FROM C
WHERE i=@

```

**Try it online**

---
Tags: code-golf, chess
---


title: Create an Accurate How-To Article

text:
# Question
Title: Create an Accurate How-To Article
Here is an easy-intermediate challenge for anyone interested!

# What is that?

A thing me and brother do a bit too often is this:

One of us has a problem and asks the other to explain how to do certain stuff. The other just says the following carelessly:

```
How to <verb> in <n> easy steps!
                                   (Newline mandatory)
Step 1 - Do not <verb>.
Step 2 - Do not <verb>.
Step 3 - Do not <verb>.
.
.
.
Step <n> - <verb>.                 (Capitalised)

```

For example, if my brother could not find a pen to write with (Do not ask me why) and asked `How do I find a pen?`, I would probably answer:

```
How to find a pen in 10 easy steps!

Step 1 - Do not find a pen.
Step 2 - Do not find a pen.
Step 3 - Do not find a pen.
Step 4 - Do not find a pen.
Step 5 - Do not find a pen.
Step 6 - Do not find a pen.
Step 7 - Do not find a pen.
Step 8 - Do not find a pen.
Step 9 - Do not find a pen.
Step 10 - Find a pen.

```

Sarcasm alert!
Now isn't that ***so*** accurate and helpful!

`<verb>` is the problem one of us wants to achieve.

`<n>` is a random number that we choose (for your information, we mostly use 10 as `<n>`, but that is not important for this challenge).

# So what?

Your challenge is to write a usual program or function using standard I/O and golfing rules that takes in a string formatted with `"How do I <v>?"` as input, and then print or return the (accurate) how-to article specified according to the rules displayed above, where `<verb>` is `<v>` from the input, and `<n>` is any random natural number from the range 1 to 10 (inclusive) generated by your program. When `<n>` is 1, remove the ending s in `...steps!`.

Standard loopholes are not allowed!

---

*Note: There might be some cases where sentences will be illogical, like in the case of `How do I find my pen?`. Outputting `How to find my pen in <n> easy steps` is fine!*

---

Here is another example for further clarity:

Input -

```
How do I make coffee?

```

*Example* output -

```
How to make coffee in 3 easy steps!

Step 1 - Do not make coffee.
Step 2 - Do not make coffee.
Step 3 - Make coffee.

```

## Good luck!

# Answer
> 14 votes
# LaTeX, 269 bytes

```
\input tikz.tex\let\s\pgfmathsetmacro\pgfmathsetseed{\number\pdfrandomseed}\def\u#1{\uppercase{#1}}\def\f
How do I #1?{\s\n{random(0,9)}\s\m{int(\n+1)}How to #1 in \m~easy
step\ifnum\m>1s!\\\\\foreach\i in{1,...,\n}{Step \i~- Do not #1.\\}\else!\\\\\fi
Step \m~- \u#1.}

```

Random numbers aren't very nice to handle in LaTeX.

Example output:

# Answer
> 9 votes
# Bash \+ coreutils seq, 128

* Thanks to @NahuelFouilleul for some good golfing suggestions.

```
v=${1:9}
v=${v%?}
s=s
echo "How to $v in $[m=(n=$$%10)+1] easy step${s::n}!

`seq -f"Step %g - Do not $v." $n`
Step $m - ${v^}."

```

Try it online!

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

Full program. Prompts for string from stdin.

```
∊'How to'(¯1↓v←8↓⌽'.'@1⌽⍞)' in'n'easy step','s!'↓⍨1=n←?10
⍬
{∊'Step'⍵'- Do not'v}⍤0⍳n-1
∊'Step'n'-',⌈@2⊢v

```

Try it online!

**ϵ**nlists (flattens) the list of components of each line. By default, numbers are printed with one spaces between them and adjacent text. Lines are implicitly printed.

The variable parts are:

### `,'s!'↓⍨1=n←?10`

`?10` random number in range 1–10
`n←` assign to `n`
`1=` is 1 equal to that? (1 if yes, 0 if no)
`'s!'↓⍨` drop that many characters from "s!"
`,` prepend the additional components on the left

### `¯1↓v←8↓⌽'.'@1⌽⍞`

prompt for string
reverse
`'.'@1` replace the character **at** index 1 with a period.
reverse
`8↓` drop the first 8 characters ("How do I")
`v←` assign to `v`
`¯1↓` drop the last character (".")

###

empty numeric list (prints as empty line)

### `{``}⍤0⍳n-1`

`n-1` subtract 1 from `n`
indices 1–(n−1)
`{``}⍤0` merge into a matrix the results from applying the following lambda on each element:
the argument (current index)

### `'Step'n'-',⌈@2⊢v`

`⊢v` on `v`
`⌈@2` uppercase the second character (there's a leading space in `v`)
`,` prepend the components

# Answer
> 6 votes
# C (gcc), 186 bytes

```
n;f(m){char*s;scanf("%m[^?]",&s);for(printf("How to%s in %d easy step%s!\n\n",memcpy(++s," Do not",7)+7,m=++n,"s"+!(n=time()%10));n--;printf("Step %d -%s.\n",m-n,(n||(1[s+=7]^=32),s)));}

```

Try it online!

*+14 bytes due to removing the last `s` in `...steps!` when `n=1`*

*-2 bytes by using `lseek`*

*-2 bytes by changing conditions*

*-1 byte by removing a space `m- --n``m-n--`*

*-3 bytes thanks to **Arnauld***

*-1 byte by changing the last condition from `n+1` to `!n`*

*-31 bytes thanks to **ErikF***

*-2 bytes by removing `s` in `%m[^?]s` and by removing space in `"Do not "`*

*-2 bytes thanks to **ceilingcat***

*-1 byte thanks to **ErikF***

# Answer
> 6 votes
# Ruby `-p`, ~~141~~ ~~140~~ ~~137~~ 131 bytes

*Saved 3 bytes by using `$$%10` instead of `rand(10)`, a golf suggested by @NahuelFouilleul in comments on other answers.*

```
$_="How to #{v=$_[9..-2]} in #{n=1+$$%10} easy ste#{:ps[0,n]}!
"+(1..n).map{|i|"
Step #{i} - #{i<n ?'Do not '+v:v.capitalize}."}*''

```

Try it online!

# Answer
> 5 votes
# C# (Visual C# Interactive Compiler), 180 bytes

```
s=>{int y=new Random().Next(10)+1,i=0;for(Write($"How to{s=s[8..^1]} in {y} easy step{(y<2?"":"s")}!\n");i++<y;)Write($"\nStep {i} - {(i<y?$"Do not"+s:(char)(s[1]^32)+s[2..])}.");}

```

-1 byte thanks to Dominic van Essen

+13 bytes due to having to remove the "s" in steps if the random number = 1.

-2 bytes due to Julian

-2 bytes due to Neil

Try it online!

# Answer
> 5 votes
# Scala, ~~195~~ 188 bytes

```
q=>{val(r,s"How do I $v?")=(math.random*10).toInt+1->q
1 to r-1 map{i=>s"Step $i - Do not $v."}mkString(s"How to $v in $r easy ste${"ps"take r}!\n\n","\n",s"\nStep $r - ${v.capitalize}.")}

```

Here it is in Scastie, but double newlines don't work there for whatever reason.

Equivalent version with newlines in TIO (modified for Scala 2.10)

# Answer
> 5 votes
# JavaScript (ES6), 159 bytes

```
s=>(g=i=>i?g(i-1)+`
Step ${i} - ${i-n?'Do not'+s:s[1].toUpperCase()+s.slice(2)}.`:`How to${s=s.slice(8,-1)} in ${n} easy step${n>1?'s':''}!
`)(n=new Date%10+1)

```

Try it online!

# Answer
> 4 votes
# C (gcc), ~~194~~ ~~193~~ ~~192~~ ~~190~~ 189 bytes

Thanks to Petr Fiedler, Neil and ceilingcat for the suggestions.

By using the method in Petr Fiedler's answer, I don't have to use counted strings and store the first character. I've never used `sscanf` to create a copy of a string before, but it really works well. (Not needed here, but another neat thing about using the `scanf` family to get a string is that you can use the `%n` specifier to get the string length at the same time!)

```
i,j;f(char*s){sscanf(s,"%m[^?]",&s);for(printf("How to%s in %d easy step%s!\n",memcpy(s+=2,"Do not",6)+6,i=++j,"s"+!(j=time(0)%10));i--;printf("\nStep %d - %s.",j-i,(i||(*(s+=7)^=32),s)));}

```

Try it online!

## Original method: 194 bytes

So that I don't have to copy the string to uppercase the first character, I grab the first character of the phrase and then adjust the start of the string to the character after that. I then print up to the character just before the question mark to complete the phrase.

```
i,j,l,c;f(char*s){for(c=*(s+=9),printf("How to %c%.*s in %d easy step%s!\n\n",c,l=strlen(++s)-1,s,i=++j,"s"+!(j=time(0)%10));i--;printf("Step %d - %s%c%.*s.\n",j-i,i?"Do not ":"",c-32*!i,l,s));}

```

Try it online!

# Answer
> 4 votes
# PowerShell Core, 188 bytes

```
$q=$args.Substring(8,"$args".Length-9)
$r=(Random 10)+1
"How to$q in $r easy step$(('s','')[$r-eq1])!`n"
1..$r|%{"Step $_ - "+("Do not$q.","$($q[1]|% t*g|% tou*t)$($q|% s*g 2).")[$_-eq$r]}

```

Line by line

1. Isolates the task  `make coffee` with the initial space
2. Generates a random number in the range 1..10
3. Prints the title with an extra new line and the conditional s
4. Prints the steps

```
{"Step $_ - "
+("Do not$q.", # if it is not the last line
"$($q[1]|% t*g|% tou*t)$($q|% s*g 2))." # if if is the last line, first char uppercase and the rest of the string
)[$_-eq$r]} # "is it the last line" condition

```

Try it online!

# Answer
> 4 votes
# CJam, 92 bytes

```
"How to "q9>);:Q" in "Amr):T" easy step"T1>'s*'!NT{"
Step "U)" - "T(U=!"do not "*Q+(eu\'.}fU

```

Try it online!

# Answer
> 3 votes
# Charcoal, ~~89~~ ~~85~~ ~~82~~ 80 bytes

```
≔✂Ｓ⁹±¹¦¹θ≔‽χηHow to θ in Ｉ⊕η easy step∧ηs¦!⸿Ｆ⊕η«⸿Step Ｉ⊕ι - ⭆⁺×Do not ‹ιηθ⎇λκ↥κ.

```

Try it online! Link is to verbose version of code. This feels ~~far too~~ long. Explanation:

```
≔✂Ｓ⁹±¹¦¹θ

```

Extract the verb from the input.

```
≔‽χη

```

Get a random number from 0 to 9, which represents the number of "Do not"s.

```
How to θ in Ｉ⊕η easy step∧ηs¦!⸿

```

Print the header, but only output the `s` if the random number wasn't 0 (1 step).

```
Ｆ⊕η«

```

Repeat for each step.

```
⸿Step Ｉ⊕ι -

```

Start a new line and print the part common to each step. (For the first step this double-spaces the list of steps from the header.)

```
⭆⁺×Do not ‹ιηθ⎇λκ↥κ

```

Except for the last step, prefix `Do not`  to the verb. Uppercase the first letter of the result.

```
.

```

Finish the step with a `.`.

# Answer
> 3 votes
# Python 3, ~~160~~ ~~170~~ ~~168~~ 167 bytes

```
p=print
a=input()[9:-1]
n=id(a)%99%10+1
s="Step %d - %%s."
p(f"How to {a} in {n} easy ste{'ps'[:n]}!\n")
for i in range(1,n):p(s%i%f"Do not {a}")
p(s%n%a.capitalize())

```

Try it online!

# Answer
> 3 votes
# Perl 5 `-n`, 129 bytes

```
chop;/I /;say"How to $' in ",$b=0|1+rand 10," easy step",'s'x($b>1),"!
";say"Step $_ - ",ucfirst"Do not "x($b>$_).$',"."for 1..$b

```

Try it online!

# Answer
> 3 votes
# Python 2, 157 bytes

```
x=input()[9:-1]
n=id(0)%19/2+1
i=1
print'How to %s in %d easy ste%s!\n'%(x,n,'ps'[:n])
exec"print'Step %d -'%i,('Do not %s.'%x)[i/n*7:].capitalize();i+=1;"*n

```

Try it online!

`id(0)%19/2+1` is not uniform, but it has a nonzero chance of giving each number, unlike `id(0)%10+1`.

# Answer
> 3 votes
# 05AB1E, 74 bytes

```
TLΩÐD≠'s×sI8.$¨©“€ß€„ÿ€† ÿ‡šŠ¥ÿ!
“ˆG®N“Š¥ ÿ - Do€–ÿ.“ˆ}®™s“Š¥ ÿ -ÿ.“ˆ¯.ª»

```

Try it online.

**Explanation:**

```
TL                   # Push a list in the range [1,10]
  Ω                  # Pop and push a random value from this list
   ÐD                # Triplicate + Duplicate, so 4 copies are on the stack
     ≠               # Check if the top copy is NOT equal to 1 (0 if 1; 1 if [2,10])
      's×           '# Repeat "s" that many times
         s           # Swap so one random integer copy is at the top again
          I          # Push the input
           8.$       # Remove the first 8 characters ("How do I")
              ¨      # Remove the last character ("?")
               ©     # Store this verb in variable `®` (without popping)
“€ß€„ÿ€† ÿ‡šŠ¥ÿ!\n“  # Push dictionary string "how toÿ in ÿ easy stepÿ!\n",
                     # where the `ÿ` are filled with the top three values on the stack
                     # from left to right
                   ˆ # Pop and add this string to the global_array
G                    # Pop another random copy, and loop `N` in the range [1, n):
 ®                   #  Push the verb from variable `®`
  N                  #  Push `N`
   “Š¥ ÿ - Do€–ÿ.“   #  Push dictionary string "step ÿ - Do not ÿ.",
                     #  where the `ÿ` are filled with the top two values again
                  ˆ  #  Pop and add this string to the global_array
}                    # After the loop:
 ®                   # Push the verb again
  .ª                 # Sentence capitalize it
    s                # Swap so another random integer copy is at the top of the stack
     “Š¥ ÿ -ÿ.“      # Push dictionary string "step ÿ - ÿ.",
                     # where the `ÿ` are once again filled automatically
               ˆ     # Pop and push this string to the global_array as well
¯                    # Then push the global_array
 .ª                  # Sentence capitalize each string (without changing existing caps)
   »                 # And join this list by newlines
                     # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `“€ß€„ÿ€† ÿ‡šŠ¥ÿ!\n“` is `"how toÿ in ÿ easy stepÿ!\n"`; `“Š¥ ÿ - Do€–ÿ.“` is `"step ÿ - Do not ÿ."`; and `“Š¥ ÿ -ÿ.“` is `"step ÿ - ÿ."`.

# Answer
> 3 votes
# Notepad++, 147 keystrokes

```
<Enter><Enter>
i<Ctrl-D><Ctrl-D><Ctrl-D><Ctrl-D><Ctrl-Shift-End><Ctrl-D><Left><Left><Ctrl-Shift-End>
<Alt-E><Down><Down><Down><Down><Down><Down><Down><Down><Down><Down><Right>r
<Right><Enter><Ctrl-F>i$<Enter><Esc><Ctrl-Shift-End><Del>
<Ctrl-G>3<Enter>
<Alt-E><Alt-C><Alt-N><Ctrl-A>1<Tab>1<Enter>
<Ctrl-H><Space>?I$<Tab><Del><Alt-A><Esc>
<Ctrl-End><Shift-Up><Ctrl-C>
<Ctrl-Home><End><Backsp><Ctrl-V><Space>easy<Space>steps!
<Left><Ctrl-Left><Up><Ctrl-Right><Shift-End><Ctrl-C>
<Ctrl-H>\d+$<Tab>Step<Space>$0<Space>-<Space><Ctrl-V>.<Alt-A>
-(.+\r)<Tab>- Do not$1<Alt-A>
(1<Space>.+p)s<Tab>$1<Alt-A><Esc>
<Right><Del><Space>in<Space><Home><Ctrl-Right><Del>t<Ctrl-Right><Del><Del>
<Ctrl-End><Shift-Home><Ctrl-Shift-Right><Ctrl-Alt-Shift-U>

```

(Newlines inserted only for ease of reading.)

### Caveats

This solution requires version 7.9 of Notepad++ (at the time of writing, the most recent version), which added keyboard shortcuts to the Column Editor window.

The solution expects:

* the question text to be in the buffer with the cursor at the end and no trailing newline;
* the file to use Windows line endings;
* the Replace dialog to have the following settings: Regular expression search ON, match whole word OFF, match case ON;
* the Column Editor dialog to have the following settings: repeat BLANK, decimal format ON;
* and the Go To dialog to be in Line mode.

I believe all of these restrictions can be worked around, at the cost of extra keystrokes.

### How??

```
<Enter><Enter>

```

Add a couple of newlines after the question text.

```
i<Ctrl-D><Ctrl-D><Ctrl-D><Ctrl-D><Ctrl-Shift-End><Ctrl-D>

```

Insert an `i` on the bottom blank line, and then use `Ctrl``D`uplicate to make it 9 lines, each containing a single `i`.

```
<Left><Left><Ctrl-Shift-End>

```

Select those lines.

```
<Alt-E><Down><Down><Down><Down><Down><Down><Down><Down><Down><Down><Right>r

```

Open the Edit menu, go down to the Convert Case submenu, and select ranDOm CasE.

(As far as I know, this is the only source of randomness in Notepad++. I have no idea why it's even in there, but it's there, so we're gonna use it.)

We now have nine lines each containing either `i` or `I` at random.

```
<Right><Enter>

```

Add a blank line at the end.

```
<Ctrl-F>i$<Enter><Esc>

```

Find the first line that contains a lowercase `i`. If there is no lowercase `i`, the cursor stays on the blank line at the end.

```
<Ctrl-Shift-End><Del>

```

Delete everything from there to the end of the file.

We now have the original question, a blank line, 0 to 9 lines of `I`, and another blank line.

```
<Ctrl-G>3<Enter>

```

Go to line 3 (the first `I` line).

```
<Alt-E><Alt-C><Alt-N><Ctrl-A>1<Tab>1<Enter>

```

Open the Column Editor dialog and insert a number at the beginning of each line from the cursor to the end of the file, starting at 1, with an increment of 1. The numbered lines will be every line with an `I` plus the blank line at the end. Thus, we end up inserting the numbers 1 to N, where N is a random number between 1 and 10.

```
<Ctrl-H><Space>?I$<Tab><Del><Alt-A><Esc>

```

Delete the `I` after each number.

```
<Ctrl-End><Shift-Up><Ctrl-C>

```

Copy the last number (N).

```
<Ctrl-Home><End><Backsp><Ctrl-V><Space>easy<Space>steps!

```

Go to the end of the first line, delete the question mark, and insert the number plus the text  `easy steps!`.

```
<Left><Ctrl-Left><Up><Ctrl-Right>

```

Position the cursor at the beginning of the first word after "How do I".

```
<Shift-End><Ctrl-C>

```

Select to the end of the line and copy (the action that I want to know how to do).

```
<Ctrl-H>

```

Replace:

```
\d+$<Tab>Step<Space>$0<Space>-<Space><Ctrl-V>.<Alt-A>

```

... each number `X` with `Step X - [action].`...

```
-(.+\r)<Tab>- Do not$1<Alt-A>

```

... the action on each instruction line except the last with `Do not [action]`...

```
(1<Space>.+p)s<Tab>$1<Alt-A><Esc>

```

... and `1 easy steps` with `1 easy step`.

```
<Right><Del><Space>in<Space>

```

Delete the newline between the action and `N easy steps` and replace it with  `in` .

```
<Home><Ctrl-Right><Del>t<Ctrl-Right><Del><Del>

```

Change `do` to `to` and delete the `I` .

```
<Ctrl-End><Shift-Home><Ctrl-Shift-Right><Ctrl-Alt-Shift-U>

```

Go to the last line, select all but the first word, and convert to sentence case. This uppercases the first character of the action (e.g. `Find a pen` instead of `find a pen`).

# Answer
> 2 votes
# Stax, 79 bytes

```
Çφ`¶J╙╜úº╢ßJ╒♂é↔1S├p$@¢☺<ME⌡┐α∟0/δ-/⌂╙Γâ∙╗-ó≡æñ↕S-α.Wì*°yf╞≈♣⌐Y/)\┬░╛₧níë╛♂9=%▀

```

Run and debug it

Can probably be shortened by a lot. I'm not too familiar with string manipulation in stax yet.

Since stax does not have a random number function, this program uses the length of the string as **n**.

# Answer
> 2 votes
# PowerShell Core, ~~163~~ 161 bytes

-2 bytes thanks @Julian

```
$q="$args"-replace'^.+I|\?$'
$r=Random 10
$s='s'*!!$r++
"How to$q in $r easy step$s!
"
1..$r|%{"Step $_ -$(' do not'*($_-ne$r)+$q-replace'^ .',{"$_"|% tou*r})."}

```

Try it online!

# Answer
> 2 votes
# Japt `-R`, 79 bytes

```
A=ö)Îç¤i`How {=s8J}  {A±1} ey ¡ep` ·cAÆi`Do not` ·i¢iUÅÎu¹gAg°X)i`Sp {X} -

```

Try it

# Answer
> 1 votes
# Red, 180 bytes

```
func[s][t: n: 0
parse s["How do I "copy t to"?"]print["How to"t"in"n:
random 10"easy steps!^/"]append t"."repeat i
n - 1[print["Step"i"- Do not"t]]t/1:
t/1 - 32 print["Step"n"-"t]]

```

Try it online!

# Answer
> 1 votes
# Pyth, 95 bytes

```
A,P>z9hOT%."\ny6¶†Õ8Âù<û¡*SŠÄ™‘uü'iyÃ",GHVtH%." t²aD–ñö«É ?6^ó",hNG;%." t8Ý§Geµè‡",HrG4

```

Try it online!

## Explanation

```
A,                                                                                # Set...
  P>z9                                                                                # ...G to the verb...
      hOT                                                                                # ...and H to the number of steps.
         %."\ny6¶†Õ8Âù<û¡*SŠÄ™‘uü'iyÃ",GH                                                    # Print "How to <G> in <H> easy steps!" with 2 trailing newlines.
                                              %." t²aD–ñö«É ?6^ó",hNG                        # Print "Step <N> - Do not <G>."...
                                           VtH                          ;                    # ...H-1 times.
                                                                         %." t8Ý§Geµè‡",HrG4 # Print "Step <H> - <G>."

```

# Answer
> 1 votes
# 05AB1E, ~~99~~ 90 bytes

*-9 bytes by using  (two-char string) and  (three-char string).*

```
ð¡3.$ðý¨U…€ß€„ .ªX«ð«„€† «TLΩ©«ð«„‡š›Ž«®i¨}…!

«®F„Š¥ ™«N>«… - «N>®QiX.ª«ë…€·€– .ª«X«}„.
«

```

Try it online!

---
Tags: code-golf, string, sequence, random
---


title: Prime Modified Z-Factorials

text:
# Question
Title: Prime Modified Z-Factorials
Let me explain one by one the above terms...

We will call \\$\text{Z-Factorial}(n)\\$ of a positive integer \\$n\\$, \\$n!\\$ (i.e. \\$n\\$ factorial) without any trailing zeros. So, \\$\text{Z-Factorial}(30)\\$ is \\$26525285981219105863630848\\$ because \\$30!=265252859812191058636308480000000\\$

We will call `Modified Z-Factorial` of \\$n\\$, the \\$\text{Z-Factorial}(n) \mod n\\$.
So, `Modified Z-Factorial` of \\$30\\$, is \\$\text{Z-Factorial}(30) \mod 30\\$ which is \\$26525285981219105863630848 \mod 30 = 18\\$

We are interested in those \\$n\\$'s for which the `Modified Z-Factorial of n` is a Prime Number

***Example***

The number \\$545\\$ is **PMZ** because \\$\text{Z-Factorial}(545) \mod 545 = 109\\$ which is prime

Here is a list of the first values of \\$n\\$ that produce `Prime Modified Z-Factorial (PMZ)`

```
5,15,35,85,545,755,815,1135,1165,1355,1535,1585,1745,1895,1985,2005,2195,2495,2525,2545,2615,2705,2825,2855,3035,3085,3155,3205,3265,3545,3595,3695,3985,4135,4315,4385,4415,4685,4705,4985,5105,5465,5965,6085,6155,6185,6385,6415,6595...

```

**Task**

The above list goes on and your task is to find the \\$k\\$th ***PMZ***

**Input**

A positive integer \\$k\\$

**Output**

The \\$kth\\$ ***PMZ***

**Test Cases**

here are some **1-indexed** test cases.
Please state which indexing system you use in your answer to avoid confusion.
Your solutions need only work within the bounds of your language's native integer size.

```
input -> output
 1        5
 10       1355
 21       2615
 42       5465
 55       7265
 100      15935
 500      84815

```

This is , so the lowest score in bytes wins.

# Answer
# Jelly,  ~~13~~  11 bytes

```
!Dt0Ḍ%⁸Ẓµ#Ṫ

```

A full program reading from STDIN which prints the result to STDOUT.

**Try it online!**

### How?

```
!Dt0Ḍ%⁸Ẓµ#Ṫ - Main Link: no arguments
         #  - set n=0 (implicit left arg) and increment getting the first
                (implicit input) values of n which are truthy under:
        µ   -   the monadic chain (f(n)):
!           -     factorial -> n!
 D          -     convert from integer to decimal digits
  t0        -     trim zeros
    Ḍ       -     convert from decimal digits to integer
      ⁸     -     chain's left argument, n
     %      -     modulo
       Ẓ    -     is prime?
          Ṫ - tail
            - implicit print

```
> 3 votes

# Answer
# 05AB1E, 16 bytes

```
[N!0ÜN%pi®>©¹Q#N

```

**Input** is **1-based** k.

**Outputs** the k-th PMZ.

Explanation:

```
[N!0ÜN%pi®>©¹Q#N
[                     Start infinite loop
 N!                   Factorial of the index
   0Ü                 Remove trailing zeros
     N%               Mod index
       p              Is prime?
        i             If it is:
         ®>©          Increment the value stored in register c (initially -1)
            ¹Q        Is the value equals the input?
              #N      If it does, push the index (which is the PMZ) and break

```

Try it online!
> 3 votes

# Answer
# Add++, 58 bytes

```
D,f,@,Rb*BDBGbUdb*!!*BFJiA%P
x:?
Wx,`y,+1,`z,$f>y,`x,-z
Oy

```

Try it online!

Times outs for \\$k \ge 30\\$ on TIO

## How it works

```
D,f,@,			; Define a function, f, taking 1 argument, n
			; Example:		STACK = [30]
	Rb*		; Factorial		STACK = [265252859812191058636308480000000]
	BD		; Convert to digits	STACK = [2 6 5 ... 0 0 0]
	BGbU		; Group adjacents	STACK = [[2] [6] [5] ... [8] [4] [8] [0 0 0 0 0 0 0]]
	db*!!		; If last is all 0s
	*BF		; 	remove it	STACK = [[2] [6] [5] ... [8] [4] [8]]
	Ji		; Join to make integer	STACK = [26525285981219105863630848]
	A%		; Mod n			STACK = [18]
	P		; Is prime?		STACK = [0]
			; Return top value	0

x:?			; Set x to the input

Wx,			; While x > 0
	`y,+1,		;	y = y + 1
	`z,$f>y,	;	z = f(y)
	`x,-z		;	x = x - z
			; We count up with y
			; If y is PMZ, set z to 1 else 0
			; Subtract z from x, to get x PMZs

Oy			; Output y

```
> 2 votes

# Answer
# Japt, 13 bytes

0-indexed. Only works, in practice, for `0` & `1` as once we go over `21!` we exceed JavaScript's `MAX_SAFE_INTEGER`.

```
ÈÊsÔsÔuX j}iU

```

Try it

```
ÈÊsÔsÔuX j}iU     :Implicit input of integer U
È                 :Function taking an integer X as argument
 Ê                :  Factorial
  s               :  String representation
   Ô              :    Reverse
    sÔ            :  Repeat (There has to be a shorter way to remove the trailing 0s!)
      uX          :  Modulo X
         j        :  Is prime?
          }       :End function
           iU     :Pass all integers through that function, returning the Uth one that returns true

```
> 2 votes

# Answer
# , ~~99~~ 93 bytes

*Edit: -6 bytes (and -4 bytes from arbitrary-precision version) thanks to Giuseppe*

```
k=scan();while(k){F=F+1;z=gamma(F+1);while(!z%%5)z=z/10;x=z%%F;k=k-(x==2|all(x%%(2:x^.5)))};F

```

Try it online!

Uses the straightforward approach, following the steps of the explanation. Unfortunately goes out of limits of 's numerical accuracy at factorial(21), so fails for any k\>2.

An arbitrary-precision version (which is not limited to small k, but is less golf-competitive) is:
**\+ gmp, 115 bytes**
> 2 votes

# Answer
# Husk, 11 bytes

```
!foṗS%ȯ↔↔ΠN

```

Try it online!

## Explanation

```
!foṗS%ȯ↔↔ΠN
 f        N filter list of natural numbers by:
         Π  take factorial
       ↔↔   reverse twice, remove trailing zeros
     S%     mod itself
    ṗ       is prime?
!           get element at index n

```
> 2 votes

# Answer
# JavaScript (Node.js),  ~~89 ... 79~~  77 bytes

```
n=>(g=y=>y%10n?(p=k=>y%--k?p(k):~-k||--n?g(x*=++i):i)(y%=i):g(y/10n))(x=i=2n)

```

Try it online!
> 1 votes

# Answer
# Python 3, ~~145~~ ~~140~~ ~~138~~ 129 bytes

```
def f(n,r=0):
 c=d=2
 while r<n:
  c+=1;d*=c
  while 1>d%10:d//=10
  i=d%c;r+=i==2or i and min(i%j for j in range(2,i))
 return c

```

Try it online!

# Python 2, ~~126~~ 125 bytes

```
def f(n,r=0):
 c=d=2
 while r<n:
	c+=1;d*=c
	while d%10<1:d/=10
	i=d%c
	r+=i==2or i and min(i%j for j in range(2,i))
 print c

```

Try it online!

---

Explanation: Keep dividing by 10 as long as the current factorial is divisible by 10, and then check the factorial modulo current number for primality.

Thanks to *caird coinheringaahing* for -20 bytes and *Dominic van Essen* for -9 bytes!
> 1 votes

# Answer
# Haskell, ~~129~~ 111 bytes

```
g n
 |n`mod`10>0=n
 |0<1=g$div n 10
f=(!!)[n|n<-[1..],let p=mod(g$product[1..n])n,[x|x<-[2..p],mod p x<1]==[p]]

```

Try it online!

`g` removes `0`s from number.

`f` takes `k`th element from an infinite list comprehension where:
`[x|x<-[2..p],mod p x==0]==[p]` is `prime` condition( compares list of divisors of `p` and a list of just p).

And `p` is `mod(g$foldr(*)1[1..n])n` the modulo of factorial passed through `g`.

Saved 18 thanks to user
> 1 votes

---
Tags: code-golf, math, primes, factorial
---


title: Reverse the truth

text:
# Question
Title: Reverse the truth
Write a program or function that:

1. takes in a string from stdio or arguments
2. replaces all occurrences of `true` with `false` and `false` with `true`
3. reverses it, but does not reverse `true` and `false`
4. returns or prints result

Examples (left side is input):

```
"true"                     "false"
"2false"                   "true2"
"true is false"            "true si false"
"false,true,undefined"     "denifednu,false,true"
"stressed-false"           "true-desserts"
"falstrue"                 "falseslaf"
"true false true x"        "x false true false"

```

Standard loopholes apply. This is , so shortest code in bytes wins.

### Leaderboard

```
var QUESTION_ID=63256,OVERRIDE_USER=20569;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
> 12 votes
# C# 6, 144 bytes

```
string R(string t)=>string.Concat(new System.Text.RegularExpressions.Regex("true|false").Replace(t,m=>m.Value[0]<'g'?"eurt":"eslaf").Reverse());

```

It uses a regular expression to match `true|false`, and if it matches `true` it will be replaced by `eslaf`, otherwise by `eurt`. `m.Value[0]<'g'` is a shorter way to say `m.Value[0]=="false"`, because the only possible values for `m.Value` are `"true"` or `"false"`, so if the char code of the first char is smaller than the char code of `'g'`, it's `"false"`.

### Old version, 95 bytes

This one had a bug, it didn't return correct output for `falstrue`.

```
string R(string t)=>string.Concat(t.Reverse()).Replace("eurt","false").Replace("eslaf","true");

```

# Answer
> 7 votes
## Bash+GNU, ~~45~~ ~~38~~ 73 bytes

**Edit:** works with both `trufalse` and `falstrue`

```
sed s/false/%eurt%/g\;s/true/%eslaf%/g|rev|sed "s/%\(true\|false\)%/\1/g"

```

**Old version**, 38 bytes (shortened, thanks to Digital Trauma):

```
rev|sed s/eurt/false/g\;s/eslaf/true/g

```

# Answer
> 7 votes
# TeaScript, ~~36~~ ~~25~~ 24 bytes

```
xv¡g("eurt|eslaf",#ln>4)

```

TeaScript is JavaScript for golfing.

Edits: Saved 11 bytes thanks to @Vɪʜᴀɴ. Fixed for input `falstrue` and saved a byte.

Old version (Invalid):

```
xv¡g("eurt",f)g(f.T¡v¡,t)

```

Explanation:

```
x    // Input
 v¡    // Reverse
   g("eurt",    // Global replace "eurt" with "false".
            f)    // f is predefined to false.
              g(f.T¡v¡, // Convert false to string, then reverse.
                       t) // t is predefined to true.

```

# Answer
> 6 votes
# JavaScript ES6, 59

As an anonymous function.

Note, replace is used just as a shorthand for match().map(). The replaced string is discarded, and the output string is made piece by piece backwards (so no need to reverse).

```
s=>s.replace(/false|true|./g,x=>s=(x[1]?x<'t':x)+s,s='')&&s

```

Test running the snippet below in an EcmaScript 6 compliant browser.

```
f=s=>s.replace(/false|true|./g,x=>s=(x[1]?x<'t':x)+s,s='')&&s

//test

console.log=x=>O.innerHTML+=x+'\n'

;[
 ["true","false"]
,["falstrue","falseslaf"]
,["1false","true1"]
,["true is false","true si false"]
,["false,true,undefined","denifednu,false,true"]
,["stressed-false","true-desserts"]
,["true false true x","x false true false"]
].forEach(t=>console.log(t[0]+' -> '+f(t[0])))
```

```
<pre id=O></pre>
```

# Answer
> 5 votes
# Windows Batch, ~~184~~ 213 bytes

Fixed the bug, `falstrue -> falseslaf` and `trufalse -> trueurt`

Probably one of the less popular languages:

```
setlocal enabledelayedexpansion
set /p Q=
set N=0
:L
call set T=%%Q:~%N%,1%%%
set /a N+=1
if not "%T%" equ "" (
set R=%T%%R%
goto L
)
set R=%R:eurt=false%
set R=%R:eslaf=true%
set R=%R:falstrue=falseslaf%
echo %R%

```

# Answer
> 5 votes
# Haskell, 94 bytes

Performs pattern matching on the input string, looking for "false" or "true" and appends the opposite to the result of applying the function on the remainder of the string. If true or false isn't found, it uses recursion to reverse the string in the same fashion.

```
f[]=[]
f('t':'r':'u':'e':s)=f s++"false"
f('f':'a':'l':'s':'e':s)=f s++"true"
f(x:s)=f s++[x]

```

# Answer
> 4 votes
# JavaScript ES6, ~~95~~ 93 bytes

Unnamed function. Add `f=` to the beginning to use it. Thanks Ismael! Also assumes that the input does not contain tabs.

```
x=>[...x[r="replace"](/false/g,"\teslaf")[r](/(\t)*true/g,"eurt")[r](/\t/g,"")].reverse().join``

```

# Answer
> 2 votes
# Julia, ~~59~~ ~~55~~ 46 bytes

```
s->replace(reverse(s),r"eurt|eslaf",i->i<"et")

```

This creates an unnamed function that accepts a string and returns a string. To call it, give it a name, e.g. `f=s->...`.

The input is reversed using `reverse`. We match on the regular expression `eurt|eslaf` which matches `true` or `false` backwards. To the match we apply a function that returns `true` if the match is lexicographically smaller than `et` (i.e. `eslaf`) and `false` otherwise. The boolean literals are converted to string in the output.

Saved 9 bytes and fixed an issue thanks to Glen O!

# Answer
> 2 votes
# Pyth, 30 bytes

```
::_z"eurt""false""eslaf""true"

```

This reverses the input (`_z`), substitutes `"eurt"` for `"false"` and `"eslaf"` for `"true"`. Replacement is done using `:`.

Try it online

# Answer
> 2 votes
# rs, 56 bytes

```
\t
+(.*\t)(.)(.*)/\2\1\3
\t/
eurt/fals\t
eslaf/true
\t/e

```

Live demo and test cases.

# Answer
> 2 votes
# Javascript, 135 Bytes

```
function(s){return s.split("").reverse().join("").replace(/eslaf/i,'☺').replace(/eurt/i,'☻').replace(/☻/g,!1).replace(/☺/g,!1)}

```

## Test:

`=>`"false is the opposite of true"

`<=`"true fo etisoppo eht si false"

*Thanks ProgramFOX and edc65 for pointing out a bug!*

# Answer
> 2 votes
# Java, ~~162~~ ~~98~~ 92 bytes

Thanks (and sorry!~) to @DanielM. for telling me about StringBuffer and the fact that we can use functions!

Because, you know, Java.

```
s->(""+new StringBuffer(s.replaceAll("false","eurt")).reverse()).replaceAll("eurt","false");
```

Returns the correct, reversed string.

Ungolfed Version:

```
s->new StringBuilder(
    s.replaceAll("false","eurt"))
    .reverse().toString().replaceAll("eurt","false");
```

Basically, I replace all instances of "false" with a backwards "true", then reverse the entire string, and then replace the now backwards versions of "true" (not the ones I just replaced) with "false". Easy peasy.

# Answer
> 1 votes
# Python 3, ~~68~~ 100 bytes

I'm still golfing it, but it's fixed to the bug, so `falstrue -> falselsaf` and `trufalse -> trueurt`

Pretty straightforward:

```
print(input()[::-1].replace("eurt","false").replace("eslaf","true").replace("falstrue","falseslaf"))

```

# Answer
> 1 votes
# Mathematica, 64 bytes

```
StringReverse@#~StringReplace~{"eurt"->"false","eslaf"->"true"}&

```

# Answer
> 1 votes
# , 40 chars / 65 bytes

```
ô[…ïċ/false|true/g,⇏[…⬯+!שúa]ù⬮ø⬯)]ù⬮ø⬯)

```

`Try it here (Firefox only).`

Thanks to @feersum for pointing out a bug!

## 21 chars / 43 bytes, non-competitive

```
ôᴙ(ïċ/⊭|⊨⌿,↪ᴙ(⬯+!ë$⸩⸩

```

`Try it here (Firefox only).`

# Answer
> 1 votes
# Haskell, 102 bytes

```
h('t':'r':'u':'e':s)="eslaf"++h s
h('f':'a':'l':'s':'e':s)="eurt"++h s
h(x:s)=x:h s
h[]=""
r=reverse.h

```

The replacement of "true" by "false" and vice-versa is quite lengthy with the pattern-matching, but at least it deals correctly with "falstrue" and the like. And besides, I suspect that a correct regex-based version would be a bit longer.

# Answer
> 1 votes
# Pyth, ~~28~~ 22

```
Amr`!dZ2jHjLGcR_Hc_z_G

```

6 bytes thanks to Jakube

Works correctly for `falstrue`, as shown in the suite below.

Test suite

# Answer
> 1 votes
## Python 3 - 108 92 bytes

```
import re
print(re.sub("eslaf|eurt",lambda m:repr(len(m.group(0))>4).lower(),input()[::-1]))

```

Uses a regex to match on "true" or "false" and uses a lambda to process matches and choose what to use as a replacement string. Using repr gets the string representation of (len(match)\>4) which gives "True" when "false" is matched and vice versa (and use .lower() because repr(bool) gives a capitalized string) to get the inverse of the match and finish up by reversing the replacement and then the processed input using \[::-1\]

Managed to get the length down 16 bytes from TFelds suggestions.

Edit: Python is back in front of java, no need for alarm.

# Answer
> 1 votes
# Japt, 26 bytes

**Note:** This may be invalid, as it requires bug fixes made after this challenge was posted.

```
Uw r"eurt|eslaf",X=>X<"et"

```

Try it in the online interpreter! (Arrow function requires ES6-compliant browser, such as Firefox.)

### How it works

```
             // Implicit: U = input string
Uw r         // reverse U, then replace:
"eurt|eslaf" // occurrences of either "eurt" or "eslaf"
X=>X<"et"    // with "false" or "true", respectively
             // Implicit: output last expression

```

Here's a version that worked before the bug fixes: (38 bytes)

```
Uw $.replace(/eurt|eslaf/g,X=>X<"et")$

```

# Answer
> 1 votes
## Gema, 43

```
*=@a{@reverse{*}};a:eurt=false;a:eslaf=true

```

(Gema is an obscure macro language.)

# Answer
> 1 votes
# Prolog, 225 bytes

```
p(X):-string_to_list(X,L),reverse(L,B),q(B,C),string_to_list(Z,C),write(Z),!.
q([],[]).
q([101,117,114,116|T],[102,97,108,115,101|L]):-q(T,L).
q([101,115,108,97,102|T],[116,114,117,101|L]):-q(T,L).
q([H|T],[H|L]):-q(T,L).

```

Try it out online here
Run by querying in the following way:

```
p("falstrue").

```

# Answer
> 1 votes
# Japt, 15 bytes

```
Ôr`laf|e¨t`Èøf

```

Try it

# Answer
> 0 votes
# Ruby, 55 bytes

```
->s{s.gsub(/true|false/){$&[?t]?:eslaf: :eurt}.reverse}

```

Test:

```
->s{s.gsub(/true|false/){$&[?t]?:eslaf: :eurt}.reverse}["false,true,undefined"]
=> "denifednu,false,true"

```

# Answer
> 0 votes
## Perl 5, 68 bytes

67 plus 1 for `-E` instead of `-e`

```
%a=(false,eurt,true,eslaf);say~~reverse<>=~s/false|true/$a{$&}/gr

```

# Answer
> 0 votes
# OpenSCAD, 178 bytes

(Note that this uses the String Theory library, as OpenSCAD doesn't exactly have a standard library. Additionally, this is a function because the only allowed input is to hard-code it.

```
use <Strings.scad>;function f(a)=contains(g(a),"eurt")?replace(g(a),"eurt","false"):g(a);function g(a)=contains(reverse(a),"eslaf")?replace(reverse(a),"eslaf","true"):reverse(a);

```

# Answer
> 0 votes
## C#, 260 bytes

```
using System;class P{static void Main(){var y=Console.ReadLine();char[] n=y.ToCharArray();Array.Reverse(n);var s=new string(n);if(s.Contains("eslaf")){s=s.Replace("eslaf","true");}if(s.Contains("eurt")){s=s.Replace("eurt","false");}Console.WriteLine(s);}}

```

# Answer
> 0 votes
## PHP, 60 bytes

Simple, reverses the string first, then replaces the reversed versions with their respective swaps.

"falstrue" becomes "eurtslaf" becomes "falseslaf".

```
<?=strtr(strrev($argv[1]),{'eurt'=>'false','eslaf'=>'true'})

```

# Answer
> 0 votes
## Perl 5.10, 54 bytes

```
$_=reverse<>;s/(eurt)|(eslaf)/$1?"false":"true"/eg;say

```

Reverse, then replace. A different way of doing it besides the hash table used for the other Perl answer, which ends up being shorter!

Try it online.

# Answer
> -1 votes
# Pyth - 18 bytes

Can be golfed a lot more.

```
Amr`!dZ2::_z_GH_HG

```

Test Suite.

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