# Question
Title: Numbers divisible by the sum and product of their digits
Take a positive integer `X`. This number is part of the sequence we are interested in if the sum of all digits of `X` is a divisor of `X`, and if the product of all digits of `X` is a divisor of `X`.

For example, `135` is such a number because `1 + 3 + 5 = 9` which divides `135 = 9 * 15` and `1 * 3 * 5 = 15` which also divides `135`.

This is sequence A038186 in the OEIS.

**Your task:** given an integer `N`, output the `N`th positive integer with such properties.

### Inputs and outputs

* Numbers may be `0`-indexed or `1`-indexed; please indicate which one your answer use.
* The input may be taken through `STDIN`, as a function argument, or anything similar.
* The output may be printed to `STDOUT`, returned from a function, or anything similar.

### Test cases

The test cases below are `1`-indexed.

```
Input        Output

1            1
5            5
10           12
20           312
42           6912
50           11313

```

### Scoring

This is , so the shortest answer in bytes wins.

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

Thanks to *Emigna* for saving a byte!

```
µNNSONSP‚ÖP½

```

Explanation:

```
µ          ½   # Get the nth number for which the following holds:
  NSO          #   The sum of digits of the current number
     NSP       #   And the products of digits of the current number
 N      ‚ÖP    #   Divides the current number
               # If the nth number has been reached, quit and implicitly print N

```

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

# Answer
> 6 votes
## Pyke, 14 bytes (non-competitive) (1-indexed)

```
~1IY'sB]im%X)@

```

Try it here!

My god what a lot of new features.

```
~1             -   infinite list of natural numbers
  IY'sB]im%X)  -  filter(^, V) - remove if any truthiness
   Y           -      digits(i)
    'sB]       -     [sum(^), product(^)]
        im%    -    map(^, %i)
           X   -   splat(^)
             @ - ^[input]

```

Of which are non-competitive

* a bugfix in `I` where it would only check if the first item on the stack was truthy
* `digits` \- return a list of digits in the number
* `@` used to get the nth item of an infinite list

Of which were being used for the first time:

* all of the above
* infinite lists

Remove the last 2 bytes to get all of these numbers.

# Answer
> 6 votes
# Jelly, 13 bytes

```
DµP;SðḍȦ
1Ç#Ṫ

```

1-based.
**TryItOnline!**

### How?

```
DµP;SðḍȦ - Link 1, test a number
D        - convert to a decimal list
 µ       - monadic chain separation
   ;     - concatenate the
  P      -     product, and the
    S    -     sum
     ð   - dyadic chain separation
      ḍ  - divides n?
       Ȧ - all (i.e. both)

1Ç#Ṫ - Main link, get nth entry, 1-based: n
1 #  - find the first n matches starting at 1 of
 Ç   - the last link (1) as a monad
   Ṫ - tail (the ultimate result)

```

# Answer
> 5 votes
# C#, 118 bytes

```
n=>{int x=0,c=0;for(;;){int s=0,p=1,i=++x;while(i>0){s+=i%10;p*=i%10;i/=10;}if((c+=p>0&&x%s+x%p<1?1:0)==n)return x;}};

```

Full program with ungolfed function and test cases:

```
using System;

public class Program
{
    public static void Main()
    {
        // x - output number
        // c - counter
        // s - sum
        // p - product
        // i - iterator
        Func<int,int>f= n=>
        {
            int x=0, c=0;
            for ( ; ; )
            {
                int s=0, p=1, i=++x;
                while (i > 0)
                {
                    s += i%10;
                    p *= i%10;
                    i /= 10;
                }
                if ( (c += p> 0&& x%s+x%p<1 ? 1 : 0) == n)
                    return x;
            }
        };

        // tests:
        Console.WriteLine(f(1));  //1
        Console.WriteLine(f(5));  //5
        Console.WriteLine(f(10)); //12
        Console.WriteLine(f(20)); //312
        Console.WriteLine(f(42)); //6912
        Console.WriteLine(f(50)); //11313
    }
}

```

# Answer
> 5 votes
# Perl 6, 44 bytes (0-indexed)

```
{grep({$_%%(.comb.sum&[*] .comb)},1..*)[$_]}

```

Explanation:

```
{                                          }  # A function, with an argument n (`$_`)
 grep(                           ,1..*)       # Filter the infinite list
      {$_                       }             # Check that the function's argument
         %%(                   )              # is divisible by
                     &                        # both:
            .comb.sum                         # - the sum of the digits
                      [*] .comb               # - the product of the digits
                                       [$_]   # Get the n-th value

```

Infinite lists ftw!

# Answer
> 5 votes
## Jellyfish, 45 bytes

```
p
\Ai
\&
>(&]&|0
  <*&d
 &~bN
  10
 ( )/+
 /*

```

Try it online!

### Explanation

This is by far the most elaborate (and also the longest) program I've written in Jellyfish so far. I have no idea whether I'll be able to break this down in an understandable manner, but I guess I'll have to try.

Jellyfish provides a fairly general iteration operator, `\`, which helps a lot with "finding the Nth *something*". One of its semantics is "iterate a function on a value until a separate test function gives something truthy" (in fact, the test function receives both the current and the last element, but we'll only make it look at the current element). We can use this to implement a "next valid number" function. Another overload of `\` is "iterate a function on a starting value N times". We can use our previous function and iterate it on `0` N times, where N is the input. All of that is set up fairly concisely with this part of the code:

```
p
\Ai
\&
>     0

```

(The reasons why `0`, the actual input to the resulting function, is over there are a bit complicated and I won't go into them here.)

The issue with all of this is, that we won't be passing the current value to the test function manually. The `\` operator will do this for us. So we now have construct a single unary function (via compositions, hooks, forks and currying) which takes a number and tells us whether it's a valid number (i.e. one which is divided by its digit sum and digit product). This is fairly non-trivial when you can't refer to the argument. Ever. It's this beauty:

```
 (&]&|
  <*&d
 &~bN
  10
 ( )/+
 /*

```

The `(` is a unary *hook*, which means that it calls the function below (`f`) on its input (the current value `x`), and then passes both of them to the test function to the right (`g`), that is it computes `g(f(x), x)`.

In our case, `f(x)` is another composite function which obtains a pair with the digit product and digit sum of `x`. That means `g` will be a function that has all three values to check if `x` is valid.

We'll start by looking at how `f` computes the digit sum and digit product. This is `f`:

```
 &~b
  10
 ( )/*
 /+

```

`&` is also composition (but the other way round). `~` is currying so `10~b` gives function that computes the decimal digits of a number, and since we're passing that to `&` from the right, that's the first thing that will happen to the input `x`. The remainder uses this list of digits to compute their sum and product.

To compute a sum, we can *fold* addition over it, which is `/+`. Likewise, to compute the product we fold multiplication over it with `/*`. To combine both of these results into a pair, we use a pair of hooks, `(` and `)`. The structure of this is:

```
()g
f

```

(Where `f` and `g` are product and sum, respectively.) Let's try to figure out why this gives us a pair of `f(x)` and `g(x)`. Note that the right hook `)` only has one argument. In this case, the other argument is implied to be `;` which wraps its arguments in a pair. Furthermore, hooks can also be used as binary functions (which will be the case here) in which case they simply apply the inner function only to one argument. So really `)` on a single function `g` gives a function that computes `[x, g(y)]`. Using this in a left hook, together with `f`, we obtain `[f(x), g(y)]`. This, in turn is used in a unary context, which mean that it's actually called with `x == y` and so we end up with `[f(x), g(x)]` as required. Phew.

That leaves only one thing, which was our earlier test function `g`. Recall that it will be called as `g([p, s], x)` where `x` is still the current input value, `p` is its digit product and `s` is its digit sum. This is `g`:

```
  &]&|
  <*&d
    N

```

To test divisibility, we'll obviously use modulo, which is `|` in Jellyfish. Somewhat unusually, it take its right-hand operand modulo its left-hand operand, which means that the arguments to `g` are already in the right order (arithmetic functions like this automatically thread over lists, so this will compute the two separate moduli for free). Our number is divisible by both the product and sum, if the result is a pair of zeros. To check whether that's the case, we treat the pair as a list of base-2 digits (`d`). The result of this is zero, only when both elements of the pair are zero, so we can negate the result of this (`N`) to obtain a truthy value for whether both values divide the input. Note that `|`, `d` and `N` are simply all composed together with a pair of `&`s.

Unfortunately, that's not the full story. What if the digit product is zero? Division and modulo by zero both return zero in Jellyfish. While this may seem like a somewhat odd convention, it actually turns out to be somewhat useful (because we don't need to check for zero before doing the modulo). However it also means we can get a false positive, if the digit sum does divide the input, but the digit product is zero (e.g. input `10`).

We can fix this by multiplying our divisibility result by the digit product (so if the digit product is zero it will turn our truthy value into a zero as well). It turns out to be simpler to multiply the divisibility result with the pair of product and sum, and extract the result from the product afterwards.

To multiply the result with the pair, we kinda need to get back at an earlier value (the pair). This is done with a *fork* (`]`). Forks are kinda like hooks on steroids. If you give them two functions `f` and `g`, they represent a binary function which computes `f(a, g(a, b))`. In our case, `a` is the product/sum pair, `b` is the current input value, `g` is our divisibility test, and `f` is the multiplication. So all of this computes `[p, s] * ([p, s] % x == [0, 0])`.

All that's left now is to extract the first value of this, which is the final value of the test function used in the iterator. This is as simple as composing (`&`) the fork with the *head* function `<`, which returns the first value of a list.

# Answer
> 4 votes
# Actually, 20 bytes

Naive implementation of the sequence definition. Golfing suggestions welcome! Try it online!

```
u`;;$♂≈;Σ(%@π(%|Y`╓N

```

**Ungolfing**

```
         Implicit input n.
u        Increment n, so that we don't accidentally include 0 in the sequence.
`...`╓   Starting with x=0, return the first n+1 values of x where f(x) is truthy.
  ;;       Duplicate x twice.
  $♂≈      str(x) and convert each char (each digit) into an int. Call this digit_list.
  ;        Duplicate digit_list.
  Σ        Get sum(digit_list).
  (%       Get x % sum(digit_list), which returns 0 if sum is a divisor of x.
  @        Swap the other duplicate of digit_list to TOS.
  π        Get prod(digit_list).
  (%       Get x % prod(digit_list), which returns 0 if prod is a divisor of x.
  |        Get x % sum(digit_list) OR x % prod(digit_list).
  Y        Logical negate, which only returns 1 if both are divisors, else 0.
N        Return the last value in the list of x where f(x) is truthy,
          that is, the nth value of the sequence.

```

# Answer
> 4 votes
## R, ~~132~~ 115 bytes

New version thanks to @Billywob nice comments !

```
n=scan();b=i=0;while(i<n){b=b+1;d=strtoi(el(strsplit(c(b,""),"")));if(na.omit(c(!b%%sum(d)&!b%%prod(d),0)))i=i+1};b

```

**Ungolfed :**

```
n=scan()
b=i=0

while(i<n)
    b=b+1;
    d=strtoi(el(strsplit(c(b,""),""))) #Splitting the number into its digits

    if(na.omit(c(!b%%sum(d)&!b%%prod(d),0)))
        i=i+1
b

```

~~Since **R** behave strangley with `NA`s, I had to add the whole `ifelse(is.na(...))` part!~~
Or use `na.omit(...)`

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

```
k=>eval("for(n=0;(E=o=>n%eval([...n+''].join(o))!=0)`+`|E`*`||--k;)++n")

```

### Demo

It tends to be slow for higher values, so I'm limiting it to 20 here.

```
let f =

k=>eval("for(n=0;(E=o=>n%eval([...n+''].join(o))!=0)`+`|E`*`||--k;)++n")

console.log(f(1));  // 1
console.log(f(5));  // 5
console.log(f(10)); // 12
console.log(f(20)); // 312
```

# Answer
> 3 votes
# Brachylog, 22 bytes

```
:1yt
#>=.@e+:I*.@e*:J*

```

Try it online!

### Explanation

```
:1y                    Evaluate the first N valid outputs to the predicate below given the
                         main input as input
   t                   The output is the last one

#>=.                  Output is a strictly positive integer
    @e+               The sum of its digits…
       :I*.           …multiplied by an integer I results in the Output
           @e*        The product of its digits…
              :J*     …multiplied by an integer J results in the Output

```

# Answer
> 3 votes
# JavaScript (ES6), 78

```
n=>eval("for(i=0;n;!p|i%s|i%p||n--)[...++i+''].map(d=>(s-=d,p*=d),s=0,p=1);i")

```

*Less golfed*

```
n=>{
  for(i=0; n; !p|i%s|i%p || n--)
    s=0,
    p=1,
    [...++i+''].map(d=>(s-=d, p*=d));
  return i
}

```

# Answer
> 3 votes
# Pyth, 18 bytes

```
e.f!.xs%LZsM*FBsM`

```

Try it online: Demonstration

### Explanation:

```
e.f!.xs%LZsM*FBsM`ZZQ1   implicit variables at the end
e                        print the last number of the
 .f                 Q1   first Q (input) numbers Z >= 1, which satisfy:
                 `Z         convert Z to a string, e.g. "124"
               sM           convert each digits back to a number, e.g. [1, 2, 4]
            *FB             bifurcate with product, e.g. [[1, 2, 4], 8]
          sM                take the sum of each, e.g. [7, 8]
       %LZ                  compute the modulo of Z with each number, e.g. [5, 4]
      s                     and add both numbers, e.g. 9
    .x             Z        if an exception occurs (mod 0), use number Z instead
   !                        test, if this number is zero

```

# Answer
> 3 votes
# Haskell, ~~94~~ ~~85~~ ~~72~~ 71 bytes

```
([n|n<-[0..],(==)=<<map(gcd n)$[product,sum]<*>[read.pure<$>show n]]!!)

```

1-indexed.

Thanks to @Zgarb for saving 13 bytes!

Thanks to @nimi for saving a byte!

# Answer
> 3 votes
# APL (Dyalog Unicode), 33 bytes

I followed an idea of @ngn when it comes to wrapping the function in some sort of a -based operation.

```
{1+⍣{0=+/((1∘⊥,×/)⍎¨⍕⍺)|⍺ ⍺}⍣⍵⊢0}

```

Explanation:

```
{1+⍣{0=+/((1∘⊥,×/)⍎¨⍕⍺)|⍺ ⍺}⍣⍵⊢0}
{1+⍣                        ⍣⍵⊢0}  ⍝ Execute the inner dfn until it returns one ⍵ times
                                   ⍝ and yield the last number it processed.
    {0=+/((1∘⊥,×/)⍎¨⍕⍺)|⍺ ⍺}       ⍝ 1 if ⍺ is divisible by sum and product of its digits.
                  ⍎¨⍕⍺             ⍝ digits of ⍺
              ,                    ⍝ a vector of...
               ×/                  ⍝ product of digits
           1∘⊥                     ⍝ sum of digits
                       |⍺ ⍺        ⍝ each modulo ⍺
     0=+/                          ⍝ both divisible?

```

Try it online!

# Answer
> 3 votes
# Vyxal, 9 bytes

```
λ₍∑ΠḊA;ȯt

```

Try it Online!

~~Apparently there's a 10 byte 0-indexed version.~~

-3 bytes from Lyxal.

# Answer
> 2 votes
# MATL, 21 bytes

```
`@tFYAtswph\~?@]NG<]&

```

Long and inefficient...

Try it online!

### How it works

```
`        % Do...while
  @      %   Push current iteration index (1-based)
  tFYA   %   Duplicate. Convert number to its digits
  ts     %   Duplicate. Sum of digits
  wp     %   Swap. Product of digits
  h\     %   Concatenate. Modulo. This gives a length-2 array
  ~?     %   If the two values are zero: we found a number in the sequence
    @    %     Push that number
  ]      %   End if
  NG<    %   True if number of elements in stack is less than input
]        % End do...while. If top of the stack is true: next iteration. Else: exit
&        % Specify only one input (top of stack) for implicit display

```

# Answer
> 2 votes
## Python3, 134 80 Bytes

New version thanks to Flp.Tkc

```
t=input();h=k=0;p=int
def g(x,q=0,w=1):
    for i in x:X=p(x);I=p(i);q+=I;w*=I
    return w!=0and X%q+X%w<1
while h<p(t):k+=1;h+=g(str(k))

```

New code, I remembered a golfing way to do the factorial

```
f,t=lambda x:0**x or x*f(x-1),0
for i in str(f(int(input()))):t+=int(i)
print(t)

```

The code itself isn't very golf-like, more like brute force golf

```
def g(x):
    q=0;w=1;X=int(x)
    for i in x:I=int(i);q+=I;w*=I
    return (w!=0+ X%q==0and X%w==0)
t=input();h=k=0
while h<int(t):
    k+=1
    if g(str(k))is True:h+=1

```

g(x) is a function that returns True if x fits the criteria.

# Answer
> 2 votes
# Python 2, ~~122~~ 110 Bytes

```
def a(m,i=1,k=1):n=map(int,`i`);p=reduce(lambda x,y:x*y,n);k+=p and 1>i%sum(n)+i%p;return(k>m)*i or a(m,i+1,k)

```

1 indexed, you need to use a Python interpreter with a quite high recursion limit.

# Answer
> 2 votes
# x86-16 machine code, 52 bytes

```
00000000: 33db 4351 8bc3 bf0a 0033 f6b1 0133 d2f7  3.CQ.....3...3..
00000010: f703 f291 f7e2 9142 e314 85c0 75ef 8bc3  .......B....u...
00000020: 33d2 f7f6 8bc3 85d2 7504 f7f1 85d2 5975  3.......u.....Yu
00000030: d1e2 cfc3                                ....

```

Listing:

```
33 DB       XOR  BX, BX         ; X = 0
        NUM_LOOP:
43          INC  BX             ; increment X
51          PUSH CX             ; save loop counter (N)
8B C3       MOV  AX, BX         ; AX = current X
        START_N:
BF 000A     MOV  DI, 10         ; DI = decimal divisor of 10
33 F6       XOR  SI, SI         ; SI = sum of digits
B1 01       MOV  CL, 1          ; CX = product of digits
        SPLIT_DIGITS:
33 D2       XOR  DX, DX         ; clear high word of dividend
F7 F7       DIV  DI             ; AX = quotient, DX = remainder
03 F2       ADD  SI, DX         ; SI = SI + digit
91          XCHG AX, CX         ; AX = running product, CX = quotient
F7 E2       MUL  DX             ; AX = AX * digit
91          XCHG AX, CX         ; CX = running product, AX = quotient
42          INC  DX             ; ZF = NZ (hacky)
E3 14       JCXZ END_N          ; if digit is a 0, end with Falsey
85 C0       TEST AX, AX         ; is quotient 0?
75 EF       JNZ  SPLIT_DIGITS   ; loop until it is
8B C3       MOV  AX, BX         ; AX = current X
33 D2       XOR  DX, DX         ; clear high word of dividend
F7 F6       DIV  SI             ; divide X by sum
8B C3       MOV  AX, BX         ; AX = current X
85 D2       TEST DX, DX         ; if sum remainder is 0 then Truthy (ZF = ZR)
75 04       JNZ  END_N          ; if not, end with Falsey (ZF = NZ)
F7 F1       DIV  CX             ; divide X by product
85 D2       TEST DX, DX         ; if product remainder is 0 then Truthy (ZF = ZR)
        END_N:
59          POP  CX             ; restore loop counter
75 D1       JNZ  NUM_LOOP       ; if falsey, keep looping and don't decrement counter
E2 CF       LOOP NUM_LOOP       ; otherwise decrement counter and loop
C3          RET                 ; return to caller

```

Callable function. Input `N` in `CX`, Output `N`th positive integer in `BX`.

`N` of `50` is about 4 seconds on an IBM PC 5150:

# Answer
> 1 votes
# Wonder, 33 bytes

```
@:^#0(!>@!(| %#0sum#0)%#0prod#0)N

```

Zero-indexed. Usage:

```
(@:^#0(!>@!(| %#0sum#0)%#0prod#0)N)9

```

# Explanation

More readable:

```
@
  iget #0
    (fltr@
      not (or % #0 sum #0) % #0 prod #0
    ) N

```

Basically gets an infinite list of numbers divisible by its digital sum and product by filtering an infinite list of whole numbers through a predicate. Then the `n`th item is simply picked out of the list.

# Answer
> 1 votes
## JavaScript (ES6), 70 bytes

```
k=(b,n=1,f=c=>n%eval([...n+''].join(c))!=0)=>f`+`|f`*`||--b?k(b,n+1):n

```

This turned out quite a bit like @Arnauld's answer, but recursion is apparently 2 bytes shorter. Works in Chrome, though it's very slow on inputs greater than 30 or so (50 takes 6 seconds).

# Answer
> 1 votes
# C89, ~~381~~ ~~226~~ ~~195~~ ~~170~~ 169 bytes

1-indexed (same exact answers as in the challenge).

**Assumes *4-byte (32 bit) `int`* (most modern architectures)**.

I genuinely believe this can't go any shorter.

```
x,c,*b,m,t,i,a;g(n){for(b=malloc(0);c<n;b[c-1]=x++,t=1){char s[9];for(i=m=0;i<sprintf(s,"%d",x);m+=a,t*=a)a=s[i++]-48;b=m*t?x%m+x%t?b:realloc(b,4*++c):b;}return b[c-1];}

```

Function `int g (int)` leaks memory and accesses uninitialised memory once per call but doesn't segfault and returns the right number.

Full program that takes input in unary (`./prog $(seq 1 10)` for 10) with ungolfed (kinda):

```
x, c, * b, m, t, i, a;

g(n) {
 for (b = malloc(0); c < n; b[c - 1] = x++, t = 1) {
  char s[9];
  i = m = 0;
  for (; i < sprintf(s, "%d", x); m += a, t *= a) a = s[i++] - 48;
  b = m * t ? x % m + x % t ? b : realloc(b, 4 * ++c) : b;
 }
 return b[c - 1];
}

main (j) {
  printf("%d\n", g(--j));
}

```

### Old answer:

### C99, 381 bytes

```
#include <stdio.h>
#include <inttypes.h>
#include <string.h>
#include <stdlib.h>
#define U uint64_t
#define S size_t
S f(S n){U x=0;S c=1,l;U*b=malloc(sizeof(U));while(c<=n){char s[21];snprintf(s,20,"%"PRIu64,x);U m=0,t=1;l=strnlen(s,21);for(S i=0;i<l;i++){U a=(U)s[i]-48;m+=a,t*=a;}if(m*t?(!(x%m))&&(!(x%t)):0){b=realloc(b,sizeof(U)*++c);b[c-1]=x;}++x;}U o=b[n];free(b);return o;}

```

This can probably be golfed more.

Full program:

```
#include <stdio.h>
#include <limits.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

bool qualifies (const uint64_t);
size_t       f (const size_t);

int main(const int argc, const char* const * const argv) {
  (void) argc;
  size_t arg = strtoull(argv[1], NULL, 10);
  uint64_t a = f(arg);
  printf("a: %" PRIu64 "\n", a);
  return 0;
}

bool qualifies (const uint64_t num) {
  char s[21];
  snprintf(s, 20, "%" PRIu64 "", num);

  uint64_t sum  = 0,
           mult = 1;
  size_t    len = strnlen(s, 400);

  for (size_t i = 0; i < len; i++) {
    uint64_t a = (uint64_t) s[i] - 48;
    sum += a, mult *= a;
  }

  //printf("sum: %" PRIu64 "\nmult: %" PRIu64 "\n", sum, mult);
  return sum * mult ? (! (num % sum)) && (! (num % mult)) : false;
}

size_t f (const size_t n) {
  uint64_t x = 0;
  size_t s_len = 1;
  uint64_t* nums = malloc(sizeof (uint64_t) * s_len);

  while (s_len <= n) {
    if (qualifies(x)) {
      ++s_len;
      //printf("len: %zu\n", s_len);
      nums = realloc(nums, sizeof (uint64_t) * s_len);
      nums[s_len - 1] = x;
    }
    ++x;
  }

  uint64_t o = nums[n];
  free(nums);
  return o;
}

```

# Answer
> 1 votes
# Julia, 81 bytes

```
n->(i=c=1;while c<n d=digits(i+=1);all(d.>0)&&i%sum(d)==i%prod(d)<1&&(c+=1)end;i)

```

This is an anonymous function that accepts an integer and returns an integer. To call it, give it a name. The approach is the obvious one: check every number until we've encountered `n` terms of the sequence. The `all` check is necessary to ensure we don't get a `DivisionError` from `%` when the product of the digits is 0.

Ungolfed:

```
function f(n)
    i = c = 1
    while c < n
        d = digits(i += 1)
        all(d .> 0) && i % sum(d) == i % prod(d) < 1 && (c += 1)
    end
    return i
end

```

Try it online! (includes all test cases)

# Answer
> 1 votes
# C, 110 bytes

```
p;s;i;j;f(n){j=0;while(n){i=++j;p=1;s=0;do p*=i%10,s+=i%10;while((i/=10)>0);if(p>0&&j%p+j%s==0)--n;}return j;}

```

Ungolfed and usage:

```
p;s;i;j;
f(n){
 j=0;
 while(n){
  i=++j;
  p=1;
  s=0;
  do
   p*=i%10,   //product
   s+=i%10;   //sum
  while((i/=10)>0);
  //check if product is not zero since floating point exception
  if(p>0 && j%p + j%s == 0)--n;
 }
 return j;
}

int main(){
 int n;
 scanf("%d",&n);
 printf("\n%d\n", f(n));
}

```

# Answer
> 1 votes
# Scala, ~~80~~ 68 bytes

```
Stream from 1 filter{n=>val x=n+""map(_-48.0);n%x.sum+n%x.product<1}

```

Try it online!

0-indexed. `Stream`s are not only infinite collections but also functions taking an `Int` and giving the element at that index.

```
Stream from 1             //Infinite stream starting at 1
  filter { n =>           //Filter each n according to this predicate:
    val x =               //List of digits
      n + ""              //Convert to string
        map(_ - 48.0);    //Turn each character into its corresponding number (as a double, so n%0 works later)
    n % x.sum +           //n modulo the sum of its digits
      n%x.product         //plus n modulo the product of its digits
      < 1                 //Make sure that's less than 1, i.e. both are 0
  }

```

# Answer
> 1 votes
# Husk, 13 bytes

```
!f§Λ`¦o§eΠΣdN

```

Try it online!

Combinators good but combinators long :(

-1 byte from Leo in SE Chat.

# Answer
> 1 votes
# APL (Dyalog Unicode), 25~~27~~ bytes

This even better answer curtesy of Adam

```
1+⍣{0=⍺|⍨(+/∧×/)⍎¨⍕⍺}⍣⎕⊢0

```

This is essentially the same just hcf is taken of the sum and product saving 2 bytes

```
1+⍣{0=∨/⍺|⍨(+/,×/)⍎¨⍕⍺}⍣⎕⊢0

```

Try it online!

```
⎕ ⍝ takes user input

{...}⍣n ⍵ ⍝ repeats the function n times

1∘+⍣{0=∨/⍺|⍨(+/,×/)⍎¨⍕⍺} ⍝ given a number repeatetly adds 1(1∘+) untill the condition is satisfied

{⍵|⍨(+/,×/)⍎¨⍕⍵} ⍝ converts numbers to a list of numbers and then take there sum and product and then take there reminder after dividing with the given number

∨/ ⍝ takes HCF of the list escecially checking if both the numbers are not zero

0= ⍝returs true if the hcf is zero

```

# Answer
> 1 votes
# Thunno 2 `ct`, 6 bytes

```
ƘçSpḊp

```

Try it online!

#### Explanation

```
ƘçSpḊp  # Implicit input, n
Ƙ       # nth positive integer, k, where:
 ç      #  Parallelly apply:
  S     #   Sum of digits of k
   p    #   Product of digits of k
    Ḋ   #  Is k divisible by them
     p  #  Both return true?
        # Implicit output

```

# Answer
> 0 votes
# PHP, 96 bytes

Takes `n` as a command line argument.

## Golfed

```
for(;$i<$argv[1];)!($p=array_product($d=str_split(++$j)))|$j%array_sum($d)||$j%$p?:$i++;echo $j;

```

## Ungolfed

```
for (; $i < $argv[1];)                             // Loop until we've found the nth number as pass by command line
    !($p = array_product($d = str_split(++$j))) || // Split our current number into its digits and assign that to a variable, then assign the product of that array to another variable.
                                                   // As well, we're checking if the product equals 0, to prevent an error from trying to mod by 0 later. The condition short circuits before it happens.
    $j % array_sum($d) ||                          // Check if the sum of the array is a divisor
    $j % $p                                        // Check if the product is a divisor
    ?: $i++;                                       // Increment the number of found instances only if all conditions are met.
echo $j;                                           // Output to screen.

```

# Answer
> 0 votes
## PowerShell v2+, 84 bytes

```
param($n)for(;$n){$n-=!(++$a%(($b=[char[]]"$a")-join'+'|iex)+$a%($b-join'*'|iex))}$a

```

Iterative solution. Takes input `$n` and enters a `for` loop so long as `$n` is not zero. Each iteration, we subtract from `$n` the result of a Boolean statement, broken out below:

```
!(++$a%(($b=[char[]]"$a")-join'+'|iex)+$a%($b-join'*'|iex))
!(                                                        ) # Encapsulate in a NOT
  ++$a%                                                     # Increment $a and take mod ...
        ($b=[char[]]"$a")                                   # Turn $a into char-array, store in $b
                         -join'+'                           # Join the char-array together with +
                                 |iex                       # and eval it
                                      $a%($b-join'*'|iex)   # Similar for *
                                     +                      # Addition

```

Thus, only if `$a%(sum)` and `$a%(product)` are *both* equal to zero will the addition also be zero, and thus the Boolean-not will be True and therefore `$n` is decremented.

Once we exit the loop (i.e., we hit the *nth* term), we simply place `$a` on the pipeline, and output is implicit.

### Examples

Note: This tosses a *bunch* of "Attempted divide by zero" errors to STDERR, which is ignored by default. I've explicitly added a `2>$null` to the example below to cleanup the output. It's also pretty slow once it gets to about `30` or so, and `50` takes about 45 seconds on my machine.

```
PS C:\Tools\Scripts\golfing> 1,5,10,20,30,42,50|%{"$_ --> "+(.\numbers-divisible-by-sum-and-product.ps1 $_ 2>$null)}
1 --> 1
5 --> 5
10 --> 12
20 --> 312
30 --> 1344
42 --> 6912
50 --> 11313

```

# Answer
> 0 votes
# BASH, 125 bytes

```
while ((n<$1));do
((i++))
p(){ fold -1<<<$i|paste -sd$1|bc;}
z=`p \*`
((z))&&[ $[i%`p +`]$[i%z] -eq 0 ]&&((n++))
done
echo $i

```

# Answer
> 0 votes
# Perl 5 `-MList::Util=sum,product -p`, 63 bytes

```
($\%sum(@a=++$\=~/./g)+$\=~/0/||$\%product@a)&&redo for 1..$_}{

```

Try it online!

`1`-indexed

# Answer
> 0 votes
# Jelly, 11 bytes

```
DS,PƊḍ¹Ạµ#Ṫ

```

Try it online!

0-indexed

```
          Ṫ  get the last element after
        µ#   counting the first (input) elements where
       Ạ     all (both) are true:
     ḍ¹      the element is divisible by
 S,P         the sum, and the products of
D            the digits

```

# Answer
> 0 votes
# Julia, 72 bytes

```
n->(i=c=1;while c<n d=digits(i+=1);c+=i%sum(d)<all(d.>0)>i%prod(d)end;i)

```

Try it online!

improvement over Alex A's answer (explanation there)

---
Tags: code-golf, sequence, arithmetic
---


title: Even sum subarrays

text:
# Question
Title: Even sum subarrays
Given an array of integers, count the number of contiguous subarrays with an even sum. You may assume that the array is non-empty, and contains only non-negative integers.

This is , so the shortest code in bytes wins.

### Test Cases

```
Input -> Output
[7] -> 0
[8] -> 1
[3, 5] -> 1
[6, 2] -> 3
[2, 4, 5] -> 3
[7, 4, 0, 5, 8] -> 6
[4, 8, 7, 9, 5] -> 7
[1, 9, 1, 0, 4] -> 7
[7, 5, 2, 1, 4, 8] -> 9
[0, 6, 6, 5, 3, 3, 8] -> 13
[8, 5, 9, 4, 5, 1, 0] -> 16

```

# Answer
> 14 votes
# Python 3.8 (pre-release), 57 bytes

```
f=lambda S,p=1:S>[]and f(S[1:])+sum((p:=p^s%2)for s in S)

```

Try it online!

Similar to brute-force method below but should have better complexity.

# Python 3, 57 bytes

```
f=lambda S:S>[]and~sum(S)%2+f(S[1:])+f(S[:-1])-f(S[1:-1])

```

Try it online!

This is a brute force method based on inclusion-exclusion. Also works on Python2.

# Python 3, 60 bytes

```
f=lambda S,e=0,i=0:e+(S>S[:i]and f(S,[e+1,i-e][S[i]&1],i+1))

```

Try it online!

This loops over the right ends of possible subarrays keeping the number of non empty even summing subarrays in `e`. The number of odd summing subarrays is implicit in `i-e` (`i` is the loop index). As we move `i` to the right we update `e` by incrementing if we pass through an even element and by replacing with the current odd summing number if we pass through an odd element. The sum of all `e`s is then output.

## Correctness and connection with @Bubbler's closed formula

This is a routine combinatorial partition. To count all (non-empty) contiguous subarrays of `S` with even sum (cswes) we split the set of all cswes into all cswes ending at `S(1)`, all cswes ending at `S(2)` etc. and add the sizes of these sets instead. If `e(n)` is the size of the set of cswes ending at `S(n)` then depending on the parity of `S(n+1)` we have `S(n+1)` even ~\> `e(n+1)=e(n)+1` and `S(n+1)` odd ~\> `e(n+1)=o(n)` where `o(n)` is the number of contiguous subarrays with odd sum ending at `S(n)`. Obviously, `o(n)+e(n)=n`. And with that we have got all the pieces used by the algorithm.

Now to connect with Bubbler's formula let us reinterpret what we are doing when going from `e(n)` to `e(n+1)`. If `S(n+1)` is even then we "increment a counter", more specifically, "the active counter". There is also an "inactive counter" which is, err, inactive. If `S(n+1)` is odd then we "swap the active and inactive counters". Which of the two counters is currently active, i.e. in `e` depends on the cumulative parity of `S` up to the current position. The counter that started out as `e(0)` therefore counts from `0` to `n0` (excl) where `n0` is as defined by Bubbler and the counter that started out as `o(0)` counts from `0` to `n1`. The algorithm adds all the steps together. Therefore, using the well-known summation formula `1+2+...+n = n(n+1)/2` we recover Bubbler's formula.

For reference, here is Bubbler's relevant comment in full:

> Fastest algorithm: prepend 0, cumulative sum, each number mod 2, then count zeros (n0) and ones (n1) and calculate n0\*(n0-1)/2+n1\*(n1-1)/2. Probably not so appealing for golf though. – Bubbler

# Answer
> 10 votes
# Python 2, 57 bytes

```
z=1
for x in input():z+=1j+1-x%2*2*z%1j
print abs(z*z)//4

```

Try it online!

Thanks to dingledooper for saving 2 bytes with `z%1j` in place of `z.real`!

**58 bytes**

```
z=p=1
for x in input():p*=1|x%-2;z+=1j+p
print abs(z*z)//4

```

Try it online!

**59 bytes**

```
t=e=o=0
for x in input():e+=1;exec"e,o=o,e;"*x;t+=e
print t

```

Try it online!

**59 bytes**

```
n=0;a=1
for x in input():n+=1;a+=1-x%2*2*a
print a*a+n*n>>2

```

Try it online!

**59 bytes**

```
p,t=l=[0,0]
for x in input():l[p]+=1;p^=x%2;t+=l[p]
print t

```

Try it online!

All these solutions iterate through the list just once. They're based on Bubbler's observation that the output can be expressed in terms of the numbers \\$(e,o)\\$ of even and odd entries in the cumulative sum as:

$$ \frac{e(e+1)+o(o-1)}{2}$$

This is because a sub-list has even sum if and only if its start and end indices correspond to elements of the same parity in the cumulative sum. The number of ways to choose two even or two odd elements in the cumulative sum is \\$\binom{c}{2}\\$, that is \\$c(c-1)/2\\$, where \\$c\\$ is their count. For evens, we need to either prepend a `0` to the cumulative sum or increase the count by 1 to account for the initial total being 0 which is even.

---

# Python, 52 bytes

```
f=lambda l,b=-1:l>[]and~sum(l)%2+f(l[1:],0)+f(l[:b])

```

Try it online!

Inspired by loopy walt's inclusion-exclusion approach. Thanks to loopy walt for -2 bytes!

We want to recursively reach all contiguous sublists of `l` to count those with even sum. We do this by repeatedly removing either the start (first) or end (last) element. But, this generates duplicate sublists because they can be reached via removals in different orders, like start then end versus end then start.

So, we guarantee that we do all start removals before any end removals. That is, once we remove the end, we no longer remove the start. We use a flag `b` for whether start removals are allowed, which starts at -1 and is set to 0 after an end removal. When `b` is 0, end removals are replaced with removing the entire list, which effectively cuts off that branch. This gives a quadratic runtime.

# Answer
> 8 votes
# 05AB1E, 4 bytes

```
ŒOÈO

```

Try it online or verify all test cases.

**Explanation:**

```
Œ     # Get the sublists of the (implicit) input-list
 O    # Sum each inner list
  È   # Check for each whether it's even
   O  # Take the sum to get the amount of truthy results
      # (after which this is output implicitly as result)

```

# Answer
> 8 votes
# Ruby, ~~59 ...~~ 37 bytes

```
->l{*q=r=0,-1;l.sum{|n|q[r^=n%2]+=1}}

```

Try it online!

Finally found the time to implement Bubbler's advice.

# Answer
> 8 votes
# APL (Dyalog Unicode), ~~15~~ 13 bytes

```
+/~2|∊+\¨,⍨\⎕

```

Try it online!

`,⍨\⎕`: Reversed prefixes of the input.
`+\¨`: For each reversed prefix, get the cumulative sums.
: Flatten into a vector of sums.
`~2|`: For each sum, is it even?
`+/`: Take the sum.

Slightly longer, but more interesting alternative:

```
+/,∘.(≤⍱2|-)⍨+\2+0,⎕

```

Try it online!

`0,⍵`: Prepend a 0 to the input.
`2+`: Add 2 to each number. This makes sure all values are positive while not changing any subsequences parities.
`+\` Take the cumulative sum. Because the vector contained only positive numbers this is strictly increasing.
`∘.( )⍨`: Make a table by applying the inner function between all pairs of values.
`+/,`: Flatten the table and sum all values.

The inner function uses NOR () and might be a bit easier to understand if rewritten with AND ():

```
(a≤b)⍱(2|a-b) ≡ (~a≤b)∧(~2|a-b) ≡ (a>b)∧(a-b is even)

```

The `a>b` makes sure each subsequence is only counted once.

# Answer
> 8 votes
# x86-64 machine code, 21 bytes

```
31 c9 f7 e1 ff c1 f6 07 01 74 02 87 d1 01 c8 af ff ce 75 f0 c3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes the address of an array of 32-bit integers in RDI and the length of the array in RSI.

Assembly:

```
.text
.global essa
.intel_syntax noprefix
essa:
    xor ecx, ecx    #
    mul ecx         # Initialise ECX, EAX, and EDX to 0.
repeat:
                    # EAX holds the running total of even-sum subarrays.
                    # ECX holds the number of even-sum subarrays ending at the current position.
                    # EDX holds the number of odd-sum subarrays ending at the current position.
    inc ecx                 # Increment the even count.
    test BYTE PTR [rdi], 1  # Check the low bit of the current number.
    jz skip                 # Jump if the low bit is 0.
    xchg ecx, edx           # (Executed if odd) Swap the counts.
skip:
    add eax, ecx            # Add the even count to the running total.
    scasd                   # Advance to the next number, and perform an unnecessary comparison.
    dec esi                 # Count down from the length of the array.
    jnz repeat              # Jump back if there is more to be processed.
    ret                     # Return.

```

# Answer
> 8 votes
# Haskell, 44 bytes

```
f a=sum[gcd 2s-1|s<-scanl1(+)=<<scanr(:)[]a]

```

Try it online!

# Answer
> 6 votes
# , 17 bytes

```
1#.1#.(0=2|+/)\\.

```

Try it online!

* `(0=2|+/)` Is sum even...
* `\\.` For each suffix list of each prefix list (so all sublists)? Returns a 0-1 matrix, and now we want to sum all the elements...
* `1#.` Sum the rows...
* `1#.` And sum the resulting list of sums.

# Answer
> 6 votes
# Jelly, 5 bytes

```
Ẇ§2ḍS

```

Try it online!

Similar to my Vyxal answer, but Jelly's builtins are nicer. A monadic link.

```
Ẇ     # Sublists
 §    # Sum (vectorised)
  2ḍ  # Is divisisible by 2? (vectorised)
    S # Sum (non-vectorising)

```

# Answer
> 6 votes
# Wolfram Language (Mathematica), ~~36~~ 34 bytes

```
Tr[1-Mod[Tr/@Subsequences@#,2]]-1&

```

–2 bytes from @alephalpha

Try it online!

There is an `EvenQ` test in Mathematica, but alephalpha's use of `Mod` saves 2 bytes relative to it:

```
Count[Tr/@Subsequences@#,_?EvenQ]-1&

```

Alternative 34-byte function from @att:

```
Count[{a__/;2∣+a}]@*Subsequences

```

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

```
#ȯ¬%2ΣQ

```

Try it online!

#### Explanation

```
      Q  # consecutive subsequences
#        # count elements by
 ȯ       # composed function
  ¬      # not
     Σ   # sum
   %2    # mod 2

```

-1 bytes thanks to ovs

# Answer
> 6 votes
# JavaScript (ES6),  ~~44~~  41 bytes

This is inspired by Bubbler's comment, but updates the sum \\$n\_0(n\_0-1)/2+n\_1(n\_1-1)/2\\$ on the fly rather than computing it afterwards. The number of 0's and 1's are stored in `a[0]` and `a[1]` respectively, with `a[]` initialized to `[1,0]`.

```
a=>a.map(c=>t+=a[p^=c&1]++,a=[1,p=t=0])|t

```

Try it online!

# Answer
> 5 votes
# Japt, 5 bytes

```
ãx èv

```

Try it

```
ãx      - subarrays reduced
   èv   - number of evens

```

# Answer
> 5 votes
# Haskell, ~~50 47~~ 44 bytes

```
g l=sum[1|t<-scanr(:)[]l>>=scanl1(+),even t]

```

Try it online!

* thanks to @ovs for reminding me there's already an *even* function in Haskell (3 Bytes saved).
* saved 3 more bytes inspired by @Lynn answer and tip for golfing in Haskell

```
sum          Total of
[1|t<-       * list comprehension counting:
scanr(:)[]l    -tails
>>=            - concatMapped to
scanl1(+)      - cumulative sum
,even t]       ? that satisfy the requirements

```

Old recursive version

```
g[]=0
g l=sum[1|t<-scanr1(+)l,even t]+g(init l)

```

```
g[]=0            empty list has 0 even sums
g l=             list has :
sum              > number of results found in:
even t             valid tails
t<-scanr1(+)l      directly reduced by +
+g(init l)       > + results of inits

```

# Answer
> 3 votes
# , ~~61~~ 57 bytes

Or **\>=4.1, 50 bytes** by replacing the word `function` with `\`.

*-4 bytes thanks to @Dominic van Essen.*

```
function(a,b=diffinv(a)%%2,`+`=sum,z=+!b,o=+b)0:z+0:o-z-o

```

Try it online!

Using @Bubbler's formula.

Without it:

### , 64 bytes

Or **\>=4.1, 57 bytes** by replacing the word `function` with `\`.

```
function(a){for(i in seq(!a))for(j in 1:i)F=F+!sum(a[j:i])%%2;F}

```

Try it online!

# Answer
> 3 votes
# , 45 bytes

```
function(a,x=table(diffinv(a)%%2))x%*%(x-1)/2

```

Try it online!

Uses Bubbler's observation and pajonk's test harness.

# Answer
> 2 votes
# Vyxal `s`, 6 bytes

```
ÞSḢƛ∑₂

```

Try it Online!

Thanks to Lyxal for this version.

```
ÞS     # Sublists
  Ḣ    # Remove the empty list at the start
   ƛ   # Map to...
    ∑₂ # Even sum?
       # (s flag) sum of all

```

# Vyxal, 8 bytes

```
ÞS'∑₂;L‹

```

Try it Online!

```
ÞS       # Sublists (Including empty array :( )
  '  ;   # Filtered by...
   ∑     # Sum...
    ₂    # Is even
      L‹ # Length of this -1 (Because empty array)

```

# Answer
> 2 votes
# Retina, ~~42~~ 27 bytes

```
.\B|\D

Y`d`01
Cw`(0|10*1)+

```

Try it online! Link includes test cases. Edit: Saved 15 bytes thanks to @m90. Explanation:

```
.\B|\D

```

Delete anything that's not the last digit of an integer.

```
Y`d`01

```

Reduce modulo 2.

```
Cw`(0|10*1)+

```

Count the number of overlapping matches with an even number of `1`s.

# Answer
> 2 votes
# Perl 5 \+ `-pal`, 56 bytes

```
$"="+";$_=map{//;grep!(1&eval"@F[$'..$_]"),$_..$#F}0..@F

```

Try it online!

---

# Perl 5 \+ `-pal -MList::Util+(sum)`, 46 bytes

```
$_=map{//;grep!(1&sum@F[$'..$_]),$_..$#F}0..@F

```

Try it online!

# Answer
> 2 votes
# TI-Basic, 27 bytes

```
fPart(.5cumSum(Ans
{2sum(Ans),1+sum(not(Ans
sum(Ans.5(Ans-1

```

Uses Bubbler's formula. Takes input in `Ans`. Output is stored in `Ans` and displayed.

# Answer
> 2 votes
# ayr, 11 bytes

Thanks to ovs's method.

```
+/|2|,+\\.I

```

# Explanation

`I` is the input (eg `6 2`) passed through the command line.

```
        \.  Suffixes decreasing in length
      +\    Cumulative sum of each
     ,      Flatten
   2|       Mod 2
  |         Not this (is the number divisible by 2?)
+/          Sum; count number of even elements

```

# Answer
> 1 votes
# JavaScript (Node.js), 89 bytes

```
f=x=>0 in x&&f(x.slice(1))+x.filter((_,i)=>~x.slice(0,i+1).reduce((s,y)=>s+y,0)&1).length

```

Try it online!

# Answer
> 1 votes
# Pari/GP, 47 bytes

```
a->sum(i=1,#a,sum(j=i,#a,!(vecsum(a[i..j])%2)))

```

Try it online!

# Answer
> 1 votes
# Factor \+ `math.unicode`, 34 bytes

```
[ all-subseqs [ Σ even? ] count ]

```

Try it online!

# Answer
> 1 votes
# Charcoal, ~~23~~ 20 bytes

```
ＩΣＥ²↨¹…№﹪Ｅ⊕Ｌθ↨¹…θλ²ι

```

Try it online! Link is to verbose version of code. Explanation: Uses @Bubbler's formula.

```
   ²                    Literal `2`
  Ｅ                     Map over implicit range
            θ           Input list
           Ｌ            Length
          ⊕             Incremented
         Ｅ              Map over implicit range
                θ       Input list
               …        Truncated to length
                 λ      Inner index
             ↨¹         Converted from base 1 i.e. summed
        ﹪               Vectorised modulo
                  ²     Literal `2`
       №           ι    Count the number of `0`s or `1`s
      …                 Exclusive range from 0
    ↨¹                  Converted from base 1 i.e. summed
 Σ                      Take the sum
Ｉ                       Cast to string
                        Implicitly print

```

Each contiguous subarray with an even sum must start and end at a point where the cumulative sums are either both even or both odd. The positions of these sums don't matter, only their counts do. The number of sums for a given count is then simply `n(n-1)/2`, since a given sum can't start and end at the same point. This is readily calculated as the sum of the exclusive range from `0` to `n`. (Both these sums are implemented as base conversion from base `1` since that returns `0` for an empty list whereas `Sum` returns `None`.)

# Answer
> 1 votes
# Excel, ~~130~~ 97 bytes

*-33 bytes applying Bubbler's formula*

```
=LET(x,COUNT(A1#),a,SEQUENCE(x),b,SUM(MOD(MMULT(A1#,(a<=TRANSPOSE(a))*1),2)),b*(b-1-x)+(x^2+x)/2)

```

Link to Spreadsheet
Rearranged Bubbler's formula to use the number of 1s and size of the original array (instead of the number of 0s). Multiplies the array by an upper triangular matrix to calculate the cumulative sums.

## Original Answer not using Bubbler's method

```
=LET(x,COUNT(A1#),a,SEQUENCE(1,x^2)-1,b,MOD(a,x)+1,c,INT(a/x)+1,d,SEQUENCE(x),SUM(1-MOD(MMULT(A1#,FILTER((d>=b)*(d<=c),b<=c)),2)))

```

### Explanation

Since Excel formulas don't really have loops, I have to get creative with in sequences in two dimensional space.
`LET(x,COUNT(A1#),` : x = number of elements
`a,SEQUENCE(1,x^2)-1,` : a = \[0..x^2\]
`b,MOD(a,x)+1,` : b = array of indices of the first items to be summed
`c,INT(a/x)+1,` : c = array of indices of the last items to be summed
`d,SEQUENCE(x),` : d = \[1..x\]
`FILTER((d>=b)*(d<=c),b<=c))` : array containing all permutations of possible consecutive sums indicated by 1 in the elements to be summed
`MMULT(A1#,~,2)` : use matrix multiplication to determine all the sums of consecutive elements
`SUM(1-MOD(~,2)))` : count the sums where the sum mod 2 = 0

# Answer
> 1 votes
# Scala, 52 bytes

```
_.tails.flatMap(_.inits)count(x=>x.size>0&x.sum%2<1)

```

Try it online!

This is a naive answer, but it didn't seem as if Bubbler's approach would be shorter, so I went with this. `_.tails.flatMap(_.inits)` first gets all subarrays that stretch to the end, then all the prefixes of those subarrays to get all subarrays of the original array.

# Answer
> 1 votes
# C (gcc), <sup>~~77~~ \\$\cdots\\$ ~~67~~</sup> 65 bytes

```
t;p;f(a)int*a;{for(int b[]={1,t=p=0};~*a;)t+=b[p^=*a++&1]++;t=t;}

```

Try it online!

*Saved ~~9~~ 11 bytes thanks to Arnauld!!!*

Inputs a pointer to an array of non-negative integers terminated by \\$-1\\$ (because pointers in C carry no length info).
Returns the number of contiguous subarrays with an even sum.

Port of Arnauld's JavaScript answer.

# Answer
> 1 votes
## Batch, 91 bytes

```
@set/at0=t=e=0,t1=-1
@for %%a in (%*)do @set/ae^^=%%a%%2&call set/at+=t%%e%%+=1
@echo %t%

```

Takes input as command-line arguments. Explanation: Rough port of @Arnauld's JavaScript answer, but starting with `[0, -1]` as preincrement is golfier.

```
@set/at0=t=e=0,t1=-1

```

Start with a cumulative total of `0`, a result of `0`, 1 even cumulative total and 0 odd cumulative totals, but with the totals decremented so that they can be preincremented.

```
@for %%a in (%*)do

```

Loop over the command-line arguments.

```
@set/ae^^=%%a%%2

```

Update the parity of the cumulative total. (`^&1` would also work for the same byte count.)

```
&call set/at+=t%%e%%+=1

```

Increment the count of even or odd cumulative totals respectively and add the new value to the final total. This has to use `call` and `%%` so that `e` gets substituted after its calculation above.

```
@echo %t%

```

Output the final total.

# Answer
> 1 votes
# Haskell, 64 bytes

```
f a=sum[div(d*d-d)2|d<-[sum[1|b<-scanl(+)0a,c b]|c<-[even,odd]]]

```

Try it online!

# Answer
> 1 votes
# Desmos, 69 bytes

Brute force method

```
L=l.length
f(l)=\sum_{n=0}^L\sum_{a=n+1}^Lmod(\sum_{b=a-n}^al[b]+1,2)

```

Try It On Desmos!

Try It On Desmos! - Prettified

### 78 bytes

Bubbler's comment

```
L=l.length
a=total(mod(\sum_{n=1}^{[1...L]}l[n],2))
b=L-a+1
f(l)=(aa-a+bb-b)/2

```

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 1 votes
# Thunno 2 `S`, 3 bytes

```
ƑʂE

```

Try it online!

#### Explanation

```
ƑʂE  # Implicit input
Ƒ    # All sublists of the input
 ʂ   # Sum each inner list
  E  # Is each sum even?
     # Implicit output of sum

```

# Answer
> 0 votes
# APL (Dyalog Classic), 25 bytes

```
{+/∊{~2|+/¨⍵}¨{,\⌽⍵}¨,\⍵}

```

Try it online!

# Answer
> 0 votes
# Burlesque, 11 bytes

```
su{++2dv}fl

```

Try it online!

```
su    # All Subsequences
{++   # Sum
 2dv  # Divisible by 2
}fl   # Number matching filter

```

---
Tags: code-golf, array, integer, subsequence
---


title: Sum of two squares

text:
# Question
Title: Sum of two squares
Given a nonnegative integer \\$n\\$, determine whether \\$n\\$ can be expressed as the sum of two square numbers, that is \\$\exists a,b\in\mathbb Z\\$ such that \\$n=a^2+b^2\\$.

```
   0 -> truthy
   1 -> truthy
   2 -> truthy
   3 -> falsy
   4 -> truthy
   5 -> truthy
   6 -> falsy
   7 -> falsy
  11 -> falsy
9997 -> truthy
9999 -> falsy

```

Relevant OEIS sequences:

This is , so shortest answer as measured in bytes wins.

# Answer
> 12 votes
# Python 3, 49 bytes

```
def f(n):[*{(n-2*x*x)**-2for x in range(n+1)}][n]

```

Try it online!

Numerics on this and the previous one may be fragile. I don't know whether `n**-2` is guaranteed to give the same value as `(-n)**-2`.

If necessary this can be fixed at the cost of 1 byte.

#### Old Python 3, 50 bytes

```
def f(n):[*{(n-2*x*x)**-2 for x in range(n+1)}][n]

```

Try it online!

### Python 3, 53 bytes

```
def f(n):[*{(n-2*x*x)**2 for x in range(n+1)}-{0}][n]

```

Try it online!

#### Old Python 3, 58 bytes

```
def f(n):[*{sorted({x*x,n-x*x})[1]for x in range(n+1)}][n]

```

Try it online!

## How

Signals by exit code: Errors out for True and returns without error for False. The error is triggered by trying to access list positions which are out of bounds if `n` is the sum of two squares. In the last two versions the special case a=b triggers a zero division error.

All versions avoid double loops. The first version does it rather clumsily by computing x^2 and n-x^2, taking the maximum and checking for collisions (by counting uniques). The convoluted way of taking the max catches the special case a=b.

The second version implements the same logic a bit smarter: instead of taking the maximum of two values it makes use of he observation that

```
`n = a^2 + b^2`

```

can be rewritten

```
`abs(n-2a^2) = abs(n-2b^2)`

```

instead of the absolute value we can also take squares. AS before we can check for collisions as long as we do not forget the special case a=b.

The last version takes the reciprocal such that the a=b case triggers a zero division error.

# Answer
> 9 votes
# , 33 bytes

```
function(n)all((n-(1:n)^2)^.5%%1)

```

Try it online!

Outputs `NA` if `n` is not the sum of 2 squares, `FALSE` if `n` is the sum of 2 squares.

If we are restricted to `TRUE`/`FALSE` output, then add +4 bytes for 37 bytes, or +3 bytes for 36 bytes if we can reverse the output.

# Answer
> 8 votes
# C (gcc), ~~88~~ ~~74~~ ~~67~~ ~~66~~ ~~64~~ 53 bytes

```
a,b;f(n){for(a=n;~a*n;b=b?--b:--a)n*=a*a+b*b!=n;a=n;}

```

-14 bytes - thanks to Kevin Cruijssen
-7 bytes - by omitting return (using global variable)
-1 byte - by using `-` instead of `!=`
-2 bytes - thanks to AZTECCO
-11 bytes - thanks to AZTECCO x2

Try it online!

# Answer
> 7 votes
# Wolfram Language (Mathematica), 15 bytes

```
2~SquaresR~#>0&

```

Try it online!

# Answer
> 7 votes
# , ~~41~~ 39 bytes

Or **\>=4.1, 32 bytes** by replacing the word `function` with a `\`.

*Edit: -2 bytes thanks to @Giuseppe.*

```
function(n)n%in%outer(k<-(0:n)^2,k,`+`)

```

Try it online!

# Answer
> 7 votes
# APL(Dyalog Unicode), 14 bytes SBCS

```
{⍵∊∘.+⍨×⍨0,⍳⍵}

```

Try it on APLgolf!

# Answer
> 6 votes
# Vyxal `RM`, 5 bytes

```
Ẋ²Ṡ=a

```

Try it Online!

```
Ẋ     # Cartesian product of (implicit range) self with (implicit range) self
 ²    # Square each
  Ṡ   # Sums of each
    a # Do any...
   =  # Equal the input?

```

# Answer
> 4 votes
# Brachylog, 7 bytes

```
~+Ċ~^₂ᵐ

```

Try it online!

If you put a variable name such as `Z` as argument, you’ll get the actual couple of values whose squared sum is the input.

### Explanation

It’s a direct description of the problem:

```
~+Ċ        Get a couple of two values Ċ whose sum is the input
  Ċ~^₂ᵐ    Both elements of Ċ must be squares of some numbers

```

# Answer
> 4 votes
# JavaScript (Node.js), 33 bytes

Returns a positive integer for Truthy, and `0` for Falsey.

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

```

Try it online!

This is a trivial modification of @MitchSchwartz's brilliant answer to *Count sums of two squares*.

### Explanation

It can be proven that if \\$ n \\$ has more \\$ 4k + 1 \\$ divisors than \\$ 4k + 3 \\$ divisors, that it can be written as the sum of two squares. One way to achieve this would be to add `1` if `n%(4*k+1)==0`, and `-1` if `n%(4*k+3)==0`. Writing this down, we can see that the task comes down to computing the following alternating sum:

```
!(n%1) - !(n%3) + !(n%5) - !(n%7) + ...

```

which can then be written as:

```
!(n%1) - (!(n%3) - (!(n%5) - (!(n%7) - ... )))`

```

The base case of `!n` handles the special case where `n=0`, by returning `1` instead.

# Answer
> 4 votes
# , 37 bytes

```
function(n,k=2^(0:n)^2)2^n%in%(k%o%k)

```

Try it online!

This checks whether \\$2^n\\$ can be written as \\$2^{a^2}\times 2^{b^2}\\$. This will rapidly run into numerical issues, but is shorter than pajonk's similar answer because we can then use `%o%` instead of `outer`. Note that Dominic's R answer remains 4 bytes shorter.

# Answer
> 4 votes
# Regex (ECMAScript or better), 37 bytes

```
^((x(x*))(?=.*(?=\2*$)(\3+$))\4|){2}$

```

Try it online! \- ECMAScript
Try it online! \- Perl
Try it online! \- Java
Try it online! \- Python
Try it online! \- Ruby
Try it online! \- PCRE
Try it online! \- .NET

Takes its input in unary, as a string of `x` characters whose length represents the number. Uses a variant of the multiplication/squaring algorithm explained in this post.

Commented and indented:

```
^                  # tail = N = input number
(                  # subtract a perfect square from tail
    # subtract a nonzero perfect square from tail
    (x(x*))        # \2 = any positive integer; \3 = \2-1; tail -= \2
    (?=
        .*         # find the smallest value of tail that satisfies the following
        (?=\2*$)   # assert \2 divides tail
        (\3+$)     # assert \3 divides tail at least once; \4 = \2*\2 - \2
    )
    \4             # along with "tail -= \2" above, acts as "tail -= \2*\2"
|
    # or just subtract 0 from tail
){2}               # do this twice
$                  # assert that tail == 0

```

This can be generalized to sums of any number of squares by changing the `2` in `{2}` to the desired count.

# Regex (Perl / Java / PCRE2 v10.34 or later / .NET), ~~21~~ 20 bytes

```
^(\1?(\2xx|^x)*){2}$

```

Try it online! / Attempt This Online! \- Perl
Try it online! / Attempt This Online! \- Java
Try it on regex101 / Attempt This Online! \- PCRE2
Try it online! \- .NET

```
^                  # tail = N = input number
(                  # The following will be captured in \1
    \1?            # Optionally subtract the previous perfect square from tail
    (\2xx|^x)*     # If on the first iteration, subtract a perfect square from tail;
                   # if on the second iteration and "\1?" was evaluated once,
                   # combines with it to subtract a perfect square from tail that
                   # is greater than or equal to the previous one; if "\1?" was
                   # evaluated zero times, this adjusts the first perfect square
                   # subtracted, optionally increasing it to a larger one, which
                   # effectively makes the "other" perfect square zero.
){2}               # Iterate this twice
$                  # Assert that tail == 0

```

# Answer
> 3 votes
# Python 3, 59 bytes

```
lambda n:n in(n and(i//n)**2+(i%n)**2for i in range(n*n+1))

```

Try it online!

# Answer
> 3 votes
# tinylisp, 125 bytes

```
(load library
(d V repeat-val
(d R(q((N)(map* *(0to N)(0to N
(q((N)(any(map* contains?(V(map* s(V N(a N 1))(R N))(a N 1))(R N

```

Try it online!

# Answer
> 3 votes
# Jelly, 6 bytes

```
ŻpŻ²§i

```

Try it online!

Outputs `0` for falsy, and a non-zero positive integer for truthy. The Footer in the TIO link simply splits the range \\$\[0, n\]\\$ into truthy (top line) and falsey (bottom line)

## How it works

```
ŻpŻ²§i - Main link. Takes n on the left
Ż      - Zero range; [0, 1, ..., n]
  Ż    - Zero range; [0, 1, ..., n]
 p     - Cartesian product
   ²   - Square everything
    §  - Sums of each pair
     i - Index of n, or 0

```

# Answer
> 2 votes
# 05AB1E, ~~8~~ 6 bytes

```
ÝãnOIå

```

Bugfixed and -2 bytes thanks to *@Mr.Xcoder*, making it now similar as *@emanresuA*'s Vyxal answer and *@cairdCoinheringaahing*'s Jelly answer.

Try it online or verify the smaller test cases.

**Explanation:**

```
Ý       # Push a list in the range [0, (implicit) input]
 ã      # Create all possible pairs with the cartesian product
  n     # Square each integer
   O    # Sum each inner pair
    Iå  # Check if this list contains the input
        # (after which the result is output implicitly)

```

# Answer
> 2 votes
# Retina 0.8.2, ~~31~~ 26 bytes

```
.+
$*
^((^1|11\2)*\1?){2}$

```

Try it online! Link includes test cases. Edit: Saved 5 bytes thanks to @Deadcode. Explanation: `^((^1|11\2)*)` matches a square number at the beginning of the string. Repeating the expression with `{2}` does not in itself change this, but it allows the use of `\1?` to add a square number matched on the first iteration. (The first stage simply converts the decimal input to unary.)

# Answer
> 2 votes
# MATL, ~~9~~ 8 bytes

```
0y&:U&+m

```

Try it online!

(Or this version for larger inputs)

1 for truthy, 0 for falsy. (Thanks to @Giuseppe for -1 byte and this neater output.)

Square every number from 0 upto the input, add all the combinations of them, and check if the input is in there. (The "larger inputs" version does the sensible - but non-golfy - thing of limiting the check upto the square root of the given number; same logic, two extra bytes, a lot less resource hunger.)

# Answer
> 2 votes
# Excel, 64 bytes

```
=LET(x,SEQUENCE(SQRT(A1)+1,,1)^2,1-AND(ISERROR(XMATCH(A1-x,x))))

```

Link to Spreadsheet

List all \\$k^2\\$ in \\$\[0..n\]\\$. Match all \\$n - k^2\\$ to list. If all matches are errors, then false, otherwise true.

# Answer
> 2 votes
# Desmos, 52 bytes

```
a=.5
f(n)=min(ceil(mod((n-[0...floor(n^a)]^2)^a,1)))

```

Try It On Desmos!

Try It On Desmos! - Prettified

### 47 bytes (doesn't work past 100 because of Desmos 10000 element restriction)

```
l=[0...n]
f(n)=min(sign([aa+bb-nfora=l,b=l])^2)

```

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 2 votes
# Octave, 25 bytes

Returns 0 for truthy and 1 for falsy. Quite short considering it's a conventional language.

```
@(n)0||(k=0:n).^2+k.^2'-n

```

Try it online!

# Answer
> 2 votes
# tinylisp, ~~125~~ ~~117~~ 109 bytes

```
(d X(q((N I)(i(l N 1)N(X(s N I)(a I 2
(d S(q((I N)(i(a(X I 1)(X(s N I)1))(i(l N I)0(S(a I 1)N))1
(q((N)(S 0 N

```

The last line is an anonymous function that takes a number and returns 1 if it is the sum of two squares, 0 otherwise. Try it online!

### Ungolfed/explanation

*Look, ma, no library!*

First, we define a helper function `X` that takes a number `N` and determines if it is (not) a square. A perfect square is the sum of consecutive odd numbers; therefore, subtracting the sum of the first several odd numbers from `N` (for an appropriate value of "several") will result in 0 if `N` is square. Thus, we recurse over increasingly large odd numbers (which we track as `I`) and subtract each one from `N` until `N` equals 0 (in which case `N` is square) or `N` is less than 0 (in which case `N` is not square):

```
(def not-square?        ; Define not-square?
  (lambda (N I)         ; as a function of two arguments:
    (if (less? N 1)     ;  If N is less than 1,
      N                 ;  return N (0 if square, negative if not square)
      (not-square?      ;  Else, recurse with these arguments:
        (sub2 N I)      ;   New N is previous N minus current odd number
        (add2 I 2)))))  ;   New I is the next odd number

```

Next, we'll define a function `S` that determines whether a number `N` is the sum of two squares. Our algorithm here is to recurse over integers `I` starting at 0: if `I` is not square, or `N` minus `I` is not square, try the next `I` until `N` is less than `I`, at which point `N` cannot be the sum of two squares. On the other hand, if `I` and `N` minus `I` are both square, then `N` is the sum of two squares.

```
(def sum-squares?           ; Define sum-squares?
  (lambda (I N)             ; as a function of two arguments:
    (if                     ;  If
      (add2                 ;   the sum of
        (not-square?        ;    0 if
          (sub2 N I)        ;    N minus I
          1)                ;    is square, < 0 otherwise
                            ;   and
        (not-square? I 1))  ;    0 if I is square, < 0 otherwise
                            ;  is truthy (nonzero), then:
      (if (less? N I)       ;   If N is less than I
        0                   ;   then return 0
        (sum-squares?       ;   Else, recurse with these arguments:
          (add2 I 1)        ;    New I is the next integer
          N))               ;    Same N
      1                     ;  Else (I and N minus I are both square), return 1

```

Finally, our submission is an anonymous function that takes `N` only and passes it to `sum-squares?` with a starting `I` of 0:

```
(lambda (N)
  (sum-squares? 0 N))

```

# Answer
> 2 votes
# Julia, ~~49~~ 35 bytes

```
~n=1 in[i^2+j^2==n for i=0:n,j=0:n]

```

Try it online!

Thanks to MarcMush we can save a lot more! We can also replace `f(n)` with the slightly shorter version `~n`!

# Answer
> 2 votes
# Julia 1.0, ~~28~~ 23 bytes

```
~n=n∈(N=(0:n).^2).+N'

```

Try it online!

Based on David Scholz’s solution.

Thanks to dingledooper for shaving 5 bytes

# Answer
> 1 votes
# Ruby, 44 bytes

```
->n{(k=0..n).any?{|a|k.any?{|b|a*a+b*b==n}}}

```

Try it online!

# Answer
> 1 votes
# Python 3.8 (pre-release), 63 bytes

```
lambda n:(r:=range(n+1))and n in(i*i+j*j for i in r for j in r)

```

Try it online!

# Answer
> 1 votes
# Charcoal, 19 bytes

```
Ｎθ≔Ｘ…·⁰θ²η⊙η⊙η⁼θ⁺ιλ

```

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

```
Ｎθ

```

Input `n`.

```
≔Ｘ…·⁰θ²η

```

Generate a list of squares from `0` to  inclusive (in case `n<2`).

```
⊙η⊙η⁼θ⁺ιλ

```

Check whether any pair sums to `n`.

# Answer
> 1 votes
# Haskell, ~~41~~ 38 bytes

```
f n=or[n==x*x+y*y|x<-[0..n],y<-[0..x]]

```

Try it online!

* Thanks to @ovs for saving 3 Bytes.

# Answer
> 1 votes
# MATLAB, 43 bytes

```
o=@(x)any(~mod(sqrt(x-(0:(x/2)^.5).^2),1));

```

taking advantage of vectorized code to search from 0 to sqrt(x/2), checking sqrt(x - i^2) is an integer with mod(\[\],1)

Try it online!

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

```
c:{0<#&x{x=+/y}/:+{(%x)=_%x}#'!2#1+x}

```

try it in the ngn/k repl

# Answer
> 1 votes
# Desmos, 47 bytes

```

f(n)=\prod_{a=0}^n\prod_{b=0}^n\{aa+bb=n:0,1\}

```

The leading newline is necessary for the piecewise to paste properly.

Outputs 0 for truthy and 1 for falsey.

Try it on Desmos!

The trick didn't work, maybe due to the `\{aa+bb=n:0,1\}` piecewise. Avoiding it with `sign(aa+bb-n)^2` or `0^{(aa+bb-n)^2}` ended up longer.

# Answer
> 0 votes
# Burlesque, 15 bytes

```
JqS[GZ2CB)++j~[

```

Try it online!

Horribly inefficient for falsy, but works

```
J   # Duplicate input (n)
qS[ # Quoted square
GZ  # Generate squares [0..n)
2CB # All combinations of pairs
)++ # Sum each pair
j   # Swap stack
~[  # n in list

```

# Answer
> 0 votes
# JavaScript (V8), 71 bytes

```
f=n=>(m=n)?[...Array(++m*m).keys()].some(i=>(i%n)**2+(~~(i/n))**2==n):0

```

Try it online!

Not great but might as well post it since I spent an hour trying.

# Answer
> 0 votes
# F#, 66 bytes

```
let a t=Seq.allPairs[0..t][0..t]|>Seq.tryFind(fun(f,s)->f*f+s*s=t)

```

Try it online!

Straight-forward: create two lists from 0 to total, `Seq.allPairs` gets the Cartesian product between the two, and `Seq.tryFind` tries to find the pair that, when squared and added together, equals the total `t`.

# Answer
> 0 votes
# Thunno 2, 6 bytes

```
Ė2Ṛ²ʂƇ

```

Try it online!

*Very* slow for large inputs.

#### Explanation

```
Ė2Ṛ²ʂƇ  # Implicit input
Ė       # Push [0..input]
 2Ṛ     # Combinations with
        # replacement with
        # a length of two
   ²    # Square (vectorised)
    ʂ   # Sum each inner list
     Ƈ  # Contains the input?
        # Implicit output

```

---
Tags: code-golf, math, decision-problem, number-theory
---


title: Element-wise string multiplication

text:
# Question
Title: Element-wise string multiplication
Inspired by this challenge (thanks @cairdcoinheringaahing for the title!), your task is to take two printable ASCII strings and multiply them element-wise with the following rules.

### How does it work?

Given two strings (for example `split` and `isbn`) you will first, truncate the longer one such that they have equal length and then determine their ASCII codes:

```
split -> spli -> [115, 112, 108, 105]
isbn  -> isbn -> [105, 115,  98, 110]

```

The next step will be to map them to the range `[0..94]` by subtracting `32` of each code:

```
[115, 112, 108, 105] -> [83, 80, 76, 73]
[105, 115,  98, 110] -> [73, 83, 66, 78]

```

Now you will multiply them element-wise modulo `95` (to stay in the printable range):

```
[83, 80, 76, 73] ⊗ [73, 83, 66, 78] -> [74, 85, 76, 89]

```

Add `32` to get back to the range `[32..126]`:

```
[74, 85, 76, 89] -> [106, 117, 108, 121]

```

And the final step is to map them back to ASCII characters:

```
[106, 117, 108, 121] -> "july"

```

### Rules

* You will write a program/function that implements the described steps on two strings and either prints or returns the resulting string
* The input format is flexible: you can take two strings, a tuple of strings, list of strings etc.
* The input may consist of one or two empty strings
* The input will be characters in the printable range (`[32..126]`)
* The output is either printed to the console or you return a string
* The output is allowed to have trailing whitespaces

### Test cases

```
"isbn", "split"                  -> "july"
"", ""                           -> ""
"", "I don't matter"             -> ""
"             ", "Me neither :(" -> "             "
"but I do!", "!!!!!!!!!"         -> "but I do!"
'quotes', '""""""'               -> 'ck_iKg'
"wood", "hungry"                 -> "yarn"
"tray", "gzip"                   -> "jazz"
"industry", "bond"               -> "drop"
"public", "toll"                 -> "fall"
"roll", "dublin"                 -> "ball"
"GX!", "GX!"                     -> "!!!"
"4 lll 4", "4 lll 4"             -> "4 lll 4"
"M>>M", "M>>M"                   -> ">MM>"

```

**Note**: The quotes are just for readability, in the 6th test case I used `'` instead of `"`.

# Answer
> 9 votes
# MATL, 12 bytes

```
c32-p95\32+c

```

**Try it online!**

### Explanation

```
c      % Implicitly input cell array of 2 strings. Convert to 2-row char matrix.
       % This pads the shorter string with spaces
32-    % Subtract 32, element-wise. Each char is interpreted as its ASCII code.
       % Note that padding spaces will give 0.
p      % Product of each column. Since (padding) spaces have been mapped to 0, the
       % product effectively eliminates those colums. So the effect is the same as
       % if string length had been limited by the shorter one
95\    % Modulo 95, element-wise
32+    % Add 32, element-wise
c      % Convert to char. Implicitly display

```

# Answer
> 6 votes
# Jelly, ~~15~~ 12 bytes

```
z⁶O_32P€‘ịØṖ

```

Try it online!

-3 thanks to Jonathan Allan.

# Answer
> 6 votes
# Python 3, ~~80~~ ~~74~~ 71 bytes

```
lambda*t:''.join(map(lambda x,y:chr((ord(x)-32)*(ord(y)-32)%95+32),*t))

```

*Thanks to @shooqie for golfing off 3 bytes!*

Try it online!

# Answer
> 5 votes
# Python 2, ~~75~~ 70 bytes

*-3 bytes thanks to Dennis' suggestion of shooqie's suggestion. -2 bytes thanks to Zacharý's suggestion.*

```
lambda*l:''.join(chr((ord(i)-32)*(ord(j)-32)%95+32)for i,j in zip(*l))

```

Try it online!

# Answer
> 5 votes
# Haskell, ~~60~~ 57 bytes

```
zipWith(\a b->toEnum$f a*f b`mod`95+32)
f=(-32+).fromEnum

```

Try it online!

First line is an anonymous function taking two arguments.

This a straight forward implementation of the algorithm: `zipWith` takes both strings and applies a given function to the pairs of characters. It handles the truncation and also works for empty strings. `fromEnum` and `toEnum` are alternatives to `ord` and `chr` to switch between characters and their ASCII values which do not need a lengthy import.

**Edit:** -3 bytes thanks to Bruce Forte.

# Answer
> 5 votes
## C++, ~~331~~ ~~291~~ ~~282~~ ~~270~~ 268 bytes, Version 2 = ~~178~~ ~~176~~ ~~150~~ 148 bytes

Original Version :

```
#include<string>
#include<algorithm>
#define L length()
#define S std::string
S m(S a,S b){S c;int m=a.L<b.L?a.L:b.L;auto l=[m](S&s){s=s.substr(0,m);std::for_each(s.begin(),s.end(),[](char&c){c-=32;});};l(a);l(b);for(int i=0;i<m;++i){c+=a[i]*b[i]%95+32;}return c;}

```

-40 bytes thanks to Bruce Forte
-39 bytes thanks to Zacharý

Version 2, inspired by other people's answers

```
#include<string>
#define L length()
using S=std::string;S m(S a,S b){S c;for(int i=0;i<(a.L<b.L?a.L:b.L);++i)c+=(a[i]-32)*(b[i]-32)%95+32;return c;}

```

If the first version uses a lambda, it's because i wanted to test C++11 std::async function i just learnt before, so i kept it for no reasons...

More readable version :

```
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

#define L length()
#define S string

//Function code for the original version
S m(S a,S b) {
    S c;
    int m = a.L < b.L ? a.L : b.L;

    auto l=[m](S&s){
        s = s.substr(0, m);
        for_each(s.begin(),s.end(),[](char&c){
            c -= 32;
        });
    };
    l(a);
    l(b);
    for(int i=0;i<m;++i) {
        c += a[i] * b[i] % 95 + 32;
    }
    return c;
}

//Code for the version 2
S m2(S a,S b) {
    S c;
    for(int i = 0; i < (a.L < b.L ? a.L : b.L); ++i) {
        c += (a[i] - 32) * (b[i] - 32) % 95 + 32;
    }
    return c;
}

int main() {
    string a, b, c;
    getline(cin, a);
    getline(cin, b);
    c = m(a, b);
    cout << c;
}

```

# Answer
> 3 votes
# Dyalog APL, ~~36~~ ~~34~~ ~~33~~ ~~25~~ 24 bytes

```
{⎕UCS 32+95|×⌿32-⎕UCS↑⍵}

```

Try it online (TryAPL)!

Try it online (TIO)!

Input is a list of strings, and has trailing whitespace.

Here's how it works:

```
{⎕UCS 32+95|×⌿32-⎕UCS↑⍵}
                     ↑⍵ - the input as a 2d array
                 ⎕UCS   - codepoints
              32-       - subtract 32
            ×⌿          - element wise product reduction ([a,b]=>a×b)
         95|            - Modulo 95
      32+               - Add 32
 ⎕UCS                   - Unicode characters

```

# Answer
> 3 votes
# FSharp 275 bytes

```
let f (p : string, q : string) =
let l = if p.Length < q.Length then p.Length else q.Length
p.Substring(0,l).ToCharArray() |> Array.mapi (fun i x -> (((int(x) - 32) * (int(q.[i]) - 32)) % 95) + 32) |> Array.map (fun x -> char(x).ToString()) |> Array.fold(+) ""

```

# Answer
> 3 votes
# 05AB1E, ~~16~~ 15 bytes

```
.BÇ32-`*₃%32+çJ

```

Try it online!

-1 for Emigna pointing out  pushes `95`.

---

```
                 # ['hi', 'you']
.B               # [['hi ', 'you']]
  Ç              # [[[104, 105, 32], [121, 111, 117]]]
   32-           # [[[72, 73, 0], [89, 79, 85]]]
      `          # [[72, 73, 0], [89, 79, 85]]
       *         # [[6408, 5767, 0]]
        ₃%       # [[43, 67, 0]]
          32+    # [[75, 99, 32]]
             ç   # [['K', 'c', ' ']]
              J  # ['Kc ']

```

---

```
.BÇ32-`*95%žQsèJ

```

is another.

# Answer
> 2 votes
# CJam, 23 bytes

```
{z{2' e]' f-:*95%' +}%}

```

Try it online!

# Answer
> 2 votes
# C# (.NET Core),100 96 95 bytes

```
(l,n)=>{for(int i=0;i<l.Length&i<n.Length;)Console.Write((char)((l[i]-32)*(n[i++]-32)%95+32));}

```

Try it online!

-4 bytes thanks to @Zacharý

-1 byte by moving the increment

Uses a lambda and abuses the fact that characters are basically ints.

# Answer
> 2 votes
# Mathematica, 114 bytes

```
(a=Min@StringLength[x={##}];FromCharacterCode[Mod[Times@@(#-32&/@ToCharacterCode/@(StringTake[#,a]&/@x)),95]+32])&

```

**input**

> \["public","toll"\]

# Answer
> 2 votes
# Stacked, 52 bytes

```
[,:$#'"!MIN$take"![CS#.toarr]"!32-prod 95%32+#:''#`]

```

Try it online!

Function that takes two arguments from the stack.

## Explanation

```
[,:$#'"!MIN$take"![CS#.toarr]"!32-prod 95%32+#:''#`]

```

Let's look at the first part, assuming the top two items are `'split'` and `'isbn'`:

```
,:$#'"!MIN$take"!      stack:                      ('split' 'isbn')
,                      pair top two:               (('split' 'isbn'))
 :                     duplicate:                  (('split' 'isbn') ('split' 'isbn'))
  $#'                  length function literal:    (('split' 'isbn') ('split' 'isbn') $#')
    "!                 execute on each:            (('split' 'isbn') (5 4))
      MIN              obtain the minimum:         (('split' 'isbn') 4)
         $take         "take" function literal:    (('split' 'isbn') 4 $take)
                       (e.g. `'asdf' 2 take` is `'as'`)
              "!       vectorized binary each:     (('spli' 'isbn'))

```

This part performs the cropping.

Then:

```
[CS#.toarr]"!     stack: (('spli' 'isbn'))
[         ]"!     perform the inside on each string
                  string `'spli'`:
 CS               convert to a character string:    $'spli'
   #.             vectorized "ord":                 (115 112 108 105)
     toarr        convert to array:                 (115 112 108 105)
                  (needed for empty string, since `$'' #.` == `$''` not `()`

```

Then, the last part:

```
32-prod 95%32+#:''#`  stack: (((115 112 108 105) (105 115  98 110)))
32-                   subtract 32 from each character code:   (((83 80 76 73) (73 83 66 78)))
   prod               reduce multiplication over the array:   ((6059 6640 5016 5694))
        95%           modulus 95:                             ((74 85 76 89))
           32+        add 32:                                 ((106 117 108 121))
              #:      convert to characters:                  (('j' 'u' 'l' 'y'))
                ''#`  join:                                   ('july')

```

# Answer
> 2 votes
# , 88 bytes

```
function(r,s,u=utf8ToInt)intToUtf8((((u(r)-32)*(u(s)-32))%%95+32)[0:min(nchar(c(r,s)))])

```

anonymous function; takes input as two strings; third argument is just to ensure this is a one line function and save some bytes.

The TIO link below returns an array with entries named with the first input.

Try all test cases!

# Answer
> 2 votes
# Perl 5, 65 bytes

64 bytes of code + `-p` flag.

```
$n=reverse<>;s/./($_=chop$n)&&chr 32+(-32+ord$&)*(-32+ord)%95/ge

```

Try it online!

# Answer
> 2 votes
# D, 113 bytes

```
T m(T)(T a,T b){T c;for(int i;i<(a.length<b.length?a.length:b.length);++i)c~=(a[i]-32)*(b[i]-32)%95+32;return c;}

```

This is a port of HatsuPointerKun's C++ solution, don't forget to upvote them!

Try it online!

# Answer
> 2 votes
# Java 8, ~~127~~ ~~115~~ ~~97~~ 95 bytes

```
a->b->{for(int i=0;i<a.length&i<b.length;System.out.printf("%c",(a[i]-32)*(b[i++]-32)%95+32));}

```

**Explanation:**

Try it here.

```
a->b->{                       // Method with 2 char-array parameters and no return-type
  for(int i=0;                //  Index-integer, starting at 0
      i<a.length&i<b.length;  //  Loop over both arrays up to the smallest of the two
    System.out.printf("%c",   //   Print, as character:
      (a[i]-32)               //    Current char of `a` minus 32
      *(b[i++]-32)            //    multiplied with current char of `b` minus 32
      %95                     //    Take modulo-95 of that multiplied result
      +32));}                 //    And add 32 again

```

# Answer
> 1 votes
# C#, 166 bytes

```
using System.Linq;s=>t=>{int e=s.Length,n=t.Length,l=e>n?n:e;return string.Concat(s.Substring(0,l).Select((c,i)=>(char)((((c-32)*(t.Substring(0,l)[i]-32))%95)+32)));}

```

I'm sure there's a lot of golfing to be done but I don't have time right now.

Try it online!

Full/Formatted Version:

```
using System;
using System.Linq;

class P
{
    static void Main()
    {
        Func<string, Func<string, string>> f = s => t =>
        {
            int e = s.Length, n = t.Length, l = e > n ? n : e;

            return string.Concat(s.Substring(0, l).Select((c, i) => (char)((((c - 32) * (t.Substring(0, l)[i] - 32)) % 95) + 32)));
        };

        Console.WriteLine(string.Concat(f("split")("isbn")));

        Console.ReadLine();
    }
}

```

# Answer
> 1 votes
# Python 2, ~~95~~ 73 bytes

* Thanks @Zacharý for 4 bytes: unwanted brackets removed

```
lambda x,y:''.join(chr((ord(i)-32)*(ord(j)-32)%95+32)for i,j in zip(x,y))

```

Try it online!

# Answer
> 1 votes
# Common Lisp, 99 bytes

```
(lambda(a b)(map'string(lambda(x y)(code-char(+(mod(*(-(#1=char-code x)32)(-(#1#y)32))95)32)))a b))

```

Try it online!

# Answer
> 1 votes
# Japt, 24 bytes

```
¬íVq)®®©c -HÃ×u95 +H dÃq

```

Returns a string with trailing null-chars (`\u0000`) when the first input is longer than the second.

Try it online! with the `-Q` flag to show formatted output, including the null-chars.

Run all the test cases using my WIP CodePen.

# Answer
> 1 votes
# Charcoal, 30 bytes

```
Ｆ⌊⟦ＬθＬη⟧℅⁺³²﹪×⁻³²℅§θι⁻³²℅§ηι⁹⁵

```

Try it online! Link is to verbose version of code. I actually wrote the calcualation as `(32 - ord(q)) * (32 - ord(h))` because it avoids consecutive numeric literals but I guess I could have just written `(ord(q) - ord(" ")) * (ord(h) - ord(" "))` instead.

# Answer
> 1 votes
# Perl 5, 95 bytes

```
@a=<>=~/(.)/g;@b=<>=~/(.)/g;$#a=$#b if@a>@b;print chr 32+(-32+ord$_)*(-32+ord$b[$i++])%95 for@a

```

Try it online!

**Explanation:**

```
@a=<>=~/(.)/g;@b=<>=~/(.)/g;  # Split the strings into 2 arrays
$#a=$#b if@a>@b;              # Truncate the first if longer than the second
print chr 32+(-32+ord$_)*(-32+ord$b[$i++])%95 for@a  # Multiply each character

```

# Answer
> 1 votes
# Pip, 19 bytes

```
(PA$* *(PA@?Zg)%95)

```

Takes the strings as command-line arguments. Try it online!

### Explanation

```
(PA$* *(PA@?Zg)%95)
                     g is list of args; PA is string of all printable ASCII characters
            Zg       Zip items of g together: result is list of pairs of characters
        PA@?         Find index of each character in PA
       (      )      (Parentheses to get correct operator precedence)
   $* *              Map (fold on *) to the list: multiplies each pair of numbers
               %95   Take list items mod 95
(PA               )  Use those numbers to index into PA again
                     Print the resulting list of chars, concatenated together (implicit)

```

# Answer
> 1 votes
# Factor, 45

```
[ [ [ 32 - ] bi@ * 95 mod 32 + ] "" 2map-as ]

```

It's a quotation (lambda), `call` it with two strings on the stack, leaves the new string on the stack.

As a word:

```
: s* ( s1 s2 -- ps ) [ [ 32 - ] bi@ * 95 mod 32 + ] "" 2map-as ;

"M>>M" "M>>M" s*      ! => ">MM>"
dup s*                ! => "M>>M"
dup s*                ! => ">MM>"
...

```

# Answer
> 1 votes
# K (oK), 26 bytes

**Solution:**

```
`c$32+95!*/-32+(&/#:'x)$x:

```

Try it online!

**Example:**

```
`c$32+95!*/-32+(&/#:'x)$x:("split";"isbn")
"july"

```

**Explanation:**

Evaluation is performed right-to-left:

```
`c$32+95!*/-32+(&/#:'x)$x: / the solution
                        x: / assign input to variable x
                       $   / pad right to length on left
               (  #:'x)    / count each x (return length of each char list in list)
                &/         / min-over, get the minimum of these counts
           -32+            / subtract 32, this automagically converts chars -> ints
         */                / multiply-over, product of the two lists
      95!                  / modulo 95
   32+                     / add 32 back again
`c$                        / convert to character array

```

# Answer
> 1 votes
# Kotlin, 65 bytes

```
{zip(it){a,b->(a-' ')*(b-' ')%95+32}.fold(""){s,i->s+i.toChar()}}

```

Try it online!

# Answer
> 1 votes
# Factor, 39 bytes

```
[ [ [ 32 - ] bi@ * 95 mod 32 + ] 2map ]

```

Try it online!

## Explanation:

This is a quotation (anonymous function) that takes two strings from the data stack and leaves one string on the data stack. In Factor, strings are just sequences of unicode code points and can be manipulated like any other sequence.

* Assuming a data stack that looks like `"split" "isbn"` when this function is called...
* `[ [ 32 - ] bi@ * 95 mod 32 + ]` push a quotation to the data stack (to be used later by `2map`) `"split" "isbn" [ [ 32 - ] bi@ * 95 mod 32 + ]`
* `2map` map over two sequences, combining them into one sequence with the given quotation which has stack effect `( x x -- x )`.
* At the beginning of the first iteration of `2map`, the data stack looks like this: `115 105`
* `[ 32 - ]` push a quotation to the data stack to be used later by the word `bi@`. `115 105 [ 32 - ]`
* `bi@` apply a quotation to the object on top of the data stack *and* the second-top object on the data stack `83 73`
* `*` multiply top two objects on the data stack `6059`
* `95` push `95` to the data stack `6059 95`
* `mod` reduce NOS (next on stack) modulo TOS (top of stack) `74`
* `32` push `32` to the data stack `74 32`
* `+` add top two objects on the data stack `106`
* So, at the end of the quotation to `2map`, we are left with `106`, which is the code point for `'j'`, which is the first element of the output sequence. The quotation given to `2map` will be run on each pair of elements until one of the two sequences no longer has any elements, meaning the output sequence will have the same size as the shorter of the two input sequences.

# Answer
> 1 votes
# Red, 81 bytes

```
func[a b][repeat i min length? a length? b[prin a/:i - 32 *(b/:i - 32)% 95 + 32]]

```

Try it online!

# Answer
> 1 votes
# Itr, 11 bytes

`32â-R*95%+¥`

Takes input as an array of 2 strings

prints additional trailing spaces if one string is longer

online interpreter

## Explanation

```
32â-R*95%+¥ ; implicit input
32          ; constant 32
  â         ; push 32 below implicit input
   -        ; subtract 32 from input
    R*      ; multiply elements of input array
      95%   ; take input modulo 95
         +  ; add 32
          ¥ ; print value as string (implicit output will print '()' for empty string)

```

# Answer
> 0 votes
# PHP, 112 bytes

```
for($i=0;$i<min(strlen($a=$argv[1]),strlen($b=$argv[2]));$i++)echo chr((ord($a[$i])-32)*(ord($b[$i])-32)%95+32);

```

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

Javascript and the curse of the lengthy function names ...

Using currying and the fact that `charCodeAt` returns `NaN` when called with an invalid position. There can be trailing nulls in the output.

```
a=>b=>a.replace(/./g,(c,i)=>String.fromCharCode((z=x=>x.charCodeAt(i)-32)(a)*z(b)%95+32))

```

**Test**

```
var f=
a=>b=>a.replace(/./g,(c,i)=>String.fromCharCode((z=x=>x.charCodeAt(i)-32)(a)*z(b)%95+32))

q=x=>'['+x+']'

;[["isbn", "split"],["", ""],["", "I don't matter"],["             ", "Me neither :("],
["but I do!", "!!!!!!!!!"],['quotes', '""""""'],["wood", "hungry"],["tray", "gzip"],
["industry", "bond"],["public", "toll"],["roll", "dublin"],["GX!", "GX!"],
["4 lll 4", "4 lll 4"],["M>>M", "M>>M"]]
.forEach(([a,b])=>console.log(q(a)+' x '+q(b)+' --> '+q(f(a)(b))))
```

# Answer
> 0 votes
# Vyxal, 16 bytes

```
øŀC32-ƒ*95%32+Cṅ

```

Try it Online!

```
øŀC32-ƒ*95%32+Cṅ  # Example input: ["wood", "hungry"]
øŀ                # Align to left by padding to the right with spaces: ["wood  ", "hungry"]
  C               # Character codes: [[119, 111, 111, 100, 32, 32], [104, 117, 110, 103, 114, 121]]
   32-            # Subtract 32: [[87, 79, 79, 68, 0, 0], [72, 85, 78, 71, 82, 89]]
      ƒ*          # Element-wise multiply both: [6264, 6715, 6162, 4828, 0, 0]
        95%       # Modulo 95: [89, 65, 82, 78, 0, 0]
           32+    # Add 32: [121, 97, 114, 110, 32, 32]
              C   # From character codes: ["y", "a", "r", "n", " ", " "]
               ṅ  # Join together: "yarn  "

```

# Answer
> 0 votes
# Ruby, 88 bytes

```
->a{c,d=a.map{_1[0,a.map(&:size).min].bytes}
c.map{((_1-32)*(d.shift-32)%95+32).chr}*""}

```

Attempt This Online!

# Answer
> 0 votes
# Thunno 2 `B`, 12 bytes

```
Z32-€p95%32+

```

Try it online!

#### Explanation

```
Z32-€p95%32+  # Implicit input (converted to ordinals)
Z             # Zip them together (truncate longer one)
 32-          # Subtract 32 (vectorised)
    €p        # Product of each inner pair
      95%     # Modulo by 95 (vectorised)
         32+  # Add 32 (vectorised)
              # Implicit output (converted to string)

```

# Answer
> 0 votes
# Zsh, 82 bytes

```
s=
repeat $#1 ((#2))&&s+=${(#)$((32+(#1-32)*(#2-32)%95))}&&1=${1:1} 2=${2:1}
<<<$s

```

Attempt This Online!

The flags needed to emulate `zip()` added too many characters, so we instead repeat for the length of the first argument, and check `((#2))` to see if we've reached the end of the second argument.

# Answer
> 0 votes
# jq, 62 bytes

```
map(explode)|transpose|map((.[0]-32)*(.[1]-32)%95?+32)|implode

```

Attempt This Online!

`transpose` fills in `null` for missing elements, we suppress those with `?`.

---
Tags: code-golf, string, printable-ascii
---