title: Never tell me the odds

text:
# Question
Title: Never tell me the odds
## Input

A integer *n* ( ≥ 1) and a digit *d* (an integer such that 0 ≤ *d* ≤ 9).

In either order; from stdin or parameters or whatever; to a program or function; etc.

## Output

The integers from 1 to *n* inclusive (in order) whose decimal representations contain an **even** number of *d*s. (That is, the integers in the list are the integers that have, respectively, an even number of *d*s.)

In any standard format, etc. In particular, the output need not be represented in decimal.

If output as a single string, the integers must be separated somehow (spaces, commas, newlines, null bytes, whatever).

## Examples

```
in(d,n) ↦ out
1,12    ↦ 2 3 4 5 6 7 8 9 11
0,111   ↦ 1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,21,22,23,24,25,26,27,28,29,31,32,33,34,35,36,37,38,39,41,42,43,44,45,46,47,48,49,51,52,53,54,55,56,57,58,59,61,62,63,64,65,66,67,68,69,71,72,73,74,75,76,77,78,79,81,82,83,84,85,86,87,88,89,91,92,93,94,95,96,97,98,99,100,111

```

## Thanks

To quintopia for the title.

# Answer
> 3 votes
# Jelly, 7 bytes

```
RDċ€Ḃ¬T

```

Try it online!

### How it works

```
RDċ€Ḃ¬T  Main link. Arguments: n, d

R        Range; yield [1, ..., n].
 D       Convert each integer in the range to base 10.
  ċ€     Count the occurrences of d in each array of decimal digits.
    Ḃ    Compute the parities.
     ¬   Negate, so even amounts evaluate to 1, odds to 0.
      T  Find all indices of truthy elements.

```

# Answer
> 13 votes
# 05AB1E, ~~11~~ 10 bytes

Code:

```
\>GN¹¢ÈiN,

```

Explanation:

```
\           # Pop input, which saves the first input into ¹
 >          # Increment on second input
  G         # For N in range(1, input + 1)
   N        # Push N
    ¹       # Push the first input from the input register
     ¢      # Count the number of occurences of the digit in N
      È     # Is even?
       iN,  # If true, print N with a newline

```

Try it online

Uses **CP-1252** encoding.

# Answer
> 13 votes
# Haskell, ~~69~~ ~~63~~ ~~52~~ 50 bytes

```
d#n=[i|i<-[1..n],even$sum[1|x<-show i,read[x]==d]]

```

Straightforwared solution for my first ever post here. It uses `show` to count the number of `d`'s. I explicitly did not use `Char` as input for `d`, which would have saved ~~12~~ 6 (after Damien's edit) bytes.

EDIT: 11 bytes less thanks to Damien! EDIT 2: another 2 bytes less thanks to nimi!

# Answer
> 12 votes
## Befunge, ~~1080~~ 945 bytes

```
vd>"000">" "v
&0      ^              p21-1+*68<
62            >        v
8           >-|        >12g68*-:|
*             >11g1+11p^        $
+                      v  <
5                         |%2g11<
5                      v.:<
+         v            <
0         >268*+12p68*11p"000"40p50p60pv
p
           v                             -1<
             v-g01p06+1g06<
>&         >:>:10g1-`     |            >:0`|
             v            <                @
             v-+55p05+1g05<
             >:54+`       |
   v               p04+g04<
  ^          <                <      <
   >60g68*-0`|      >50g68*-0`|
             >" "60p^         >" "50p^

```

The score is given that we count the entire square, including newlines, which makes sense. You can copy paste the code into the interpeter. Provide two inputs, first *d* and then *n*. This solution does not work for values larger than *n* \> 999.

This will obviously not be a contender for the grand prize, but I've been wanting to implement a codegolf in Befunge for a while now, so I decided to just do it. I figure this will not be even close to an optimal Befunge solution, as it is the first actual thing I've done in Befunge. So, hints are welcome, if you need clarification or more information, please let me know in the comments.

## Attempt at explanation:

In the first column downward we read an integer from the input, add 48 (6\*8, you'll see this more often) to it to convert it to the corresponding ASCII value and puts it to `(10, 0)`.

`&` \- read input

`68*+` \- add 48

`55+0p` \- put the value at `(10, 0)`

Note that the `d` at `(1, 0)` is just an easy way to get the number 100 on the stack.

After that, we go east and read another integer and head in to what I call the ASCIIfier. This turns the current number into a series of ASCII characters. The ASCIIfier is the rectangular piece from `(13, 12)` to `(26, 17)`. It consists of two loops, first counting the hunderds and than the tens and putting them into the three digits at `(6, 0)` and `(5, 0)`. After that the last digit is put into `(4, 0)`. So the numbers is actually in reverse.

```
v-g01p06+1g06< - increment the "hunderds counter" located at (0, 6) and decrease current value by 100
>:10g1-`     | - ASCIIfier entry; check if the current value is > 99, if so, go up, else go down
v            < - go to start of "tens counter"
v-+55p05+1g05< - increment the "tens counter" located at (0, 5) and decrease current value by 10
>:54+`       | - check if current value is > 9, if so, go up, else go down
      p04+g04< - put the final value into the "singles counter" located at (0, 4)

```

After putting the current integer into a series of ASCII characters, we go a bit more south to remove prepended zeroes. Thus, afterwards, what are initially the three zeroes at the top, will be the current number, without prepended zeroes.

Then we go back up, all the way to the North, where we put the three digits on the stack. We iterate over the three digits in the top loop, each time incrementing the counter located at `(1, 1)` if the current digit corresponds with the input *d*

When that is done we go and check to see if the counter that located at `(1, 1)` is odd or even. If it is even, we output the current number and move on to the big outer loop to decrement the current value and start over again.

# Answer
> 7 votes
## Python 2, 50 bytes

```
f=lambda d,n:n*[0]and f(d,n-1)+~`n`.count(d)%2*[n]

```

A recursive function that takes the digit `d` as a string and the upper bound `n` as a number.

The count of digits `d`'s in `n` is tested to be even by taking it's bit complement modulo 2, which gives `1` for even and `0` for odd. This many `n`'s are appending to the list, and the function recurse down to `n-1`, stopping via logical short-circuit on the empty list when `n==0`.

If the output may be given in decreasing order, one byte can be saved, for 49 bytes:

```
f=lambda d,n:n*[0]and~`n`.count(d)%2*[n]+f(d,n-1)

```

---

**Old 51-byte solution:**

```
lambda d,n:[x+1for x in range(n)if~`~x`.count(d)&1]

```

An anonymous function that takes the digit `d` as a string and the upper bound `n` as a number.

Two tricks are used:

* Python's `range` is zero-indexed `0...n-1`, so we add one to each potential value `x`. Then, to count `d`'s in `x+1`, it saves a character to use its negation `~x` instead.
* To filter for even values, we do `~_%2`, which first bit-flips to switch parity, then takes the last bit with `&1` (same as `%2` here), producing a truthy value only if the original was even.

# Answer
> 4 votes
# Pyth, 10 bytes

```
f!%/`Tz2SE

```

Try it online. Test suite.

# Answer
> 4 votes
## Lua, 86 Bytes

If using inconsistent separator is allowed, I could replace `io.write` by `print`, meaning numbers would be separated by one or multiple newlines.

This is a full program, which have to be called like this: `lua file.lua d n`.

It removes all non-`d` character from the current number and uses the size of the resulting string to decide weither or not it should be outputed.

```
for i=1,0+arg[2]do io.write(#(i..''):gsub("[^"..arg[1].."]","")%2<1 and i.." "or"")end

```

# Answer
> 4 votes
# JavaScript (ES6) 64

An anonymous function with output to console. Straightforward implementation using `split` to count the digits.

```
(d,n)=>{for(i=0;i++<n;)(i+'').split(d).length&1&&console.log(i)}

```

Output using `alert` would be 6 byte less, but I really don't like it (and I'm not going to beat the toy languages anyway)

# Answer
> 4 votes
# MATL, ~~12~~ 10 bytes

```
:!V!=s2\~f

```

First input is *n*, second is *d* as a string. For example:

```
12
'1'

```

**Try it online!**

```
:       % implicitly take input n (number). Generate row vector [1,2,...,n]
!       % transpose into column vector
V       % convert each number to string. Gives 2D char array padded with spaces
!       % transpose
=       % implicitly take input d (string). Compare with each element of the array
s       % sum of each column: number of coincidences with d
2\~     % true for even values
f       % find indices of true values. Implicitly display

```

# Answer
> 4 votes
# Ruby, ~~47~~ 42 bytes

```
?1.upto $*[1]{|s|s.count($*[0])%2<1&&p(s)}

```

Run with *d* and *n* as command-line parameters, e.g.

```
ruby golf.rb 1 12

```

# Answer
> 4 votes
# PowerShell, ~~62~~ 55

```
param($1,$2);1..$2|?{!(([char[]]"$_"-match$1).Count%2)}

```

edit: using a param block in this case is shorter. removed some redundant space

---

Not a golfing language but its the only one I really know. This would work saved as a script and called like this `M:\Scripts\cgNeverTellMeTheOdds.ps1 1 12`. First argument is the digit *d* and the second is integer *n*.

Create an array of number 1 to *n*. For each of those convert that into a character array. 10 would be 1,0. Using `-match` as an array operator return all the elements that match the digit *d*. Count the amount of elements returned and mod 2 the result. Result will be 0 for even and 1 for odd. 0 as a boolean is false so we use `!` for the loop to evaluate the odd results to false and even results to true.

Output is a newline delimited on console.

# Answer
> 3 votes
# Bash + GNU utilities, 37

* 1 byte saved thanks to @Ruud.

```
seq $1|egrep "^[^$2]*($2[^$2]*){2}*$"

```

# Answer
> 3 votes
# Retina, ~~99~~ 105 bytes

Note the trailing spaces. `<empty>` represents an empty line.

```
\d+$
$*
+`^(. )(1*)1\b
$1$2 1$2
1+
$.0
+`^(.)(.*) ((?!\1)\d)*\1((?!\1)\d|(\1)((?!\1)\d)*\1)*\b
$1$2
^.
<empty>

```

Takes input like `1 12`. Output is space separated in decreasing order.

I modified `0*1(0|10*1)*` to match an odd number of `\1` in a number. I changed `0` to `(?!\1)\d`, and `1` to `\1` to create the long regex line you see above. Understanding how the linked regex works is crucial.

**Try it online**

### Commented explanation of old version

If descending order were okay

```
\d+$            Convert last number N to unary
$*
+`1(1*)$        Create list N N-1 ... 1 in unary
$0 $1
 (1)+           Convert back to decimal
 $#1
+`^(.)(.*) ((?!\1)\d)*\1((?!\1)\d|(\1)((?!\1)\d)*\1)*   Remove numbers w/ odd num of D's
$1$2
^.              Remove first parameter
<empty>

```

# Answer
> 3 votes
# Python 3.4, 92 85 79 85 bytes

*Saved 7 bytes thanks to Mego*
*Saved another 6 bytes thanks to mbomb007*
*Regained those 6 bytes because Python 3.x*

This is my first shot at code golf, so here goes nothing!

```
lambda n,d:[i for i in range(n+1)if len([j for j in list(str(i))if j==str(d)])%2is 0]

```

# Answer
> 2 votes
# Perl 6, 38 bytes

```
{(1..$^n).grep(*.comb.Bag{~$^d} %% 2)}

```

# Answer
> 2 votes
# Brachylog, 32 bytes

```
:1reIlL,"":Ic:.xl-L=%2=0,Iw,@Sw\

```

Expects N as input and the digit as output, e.g. `brachylog_main(12,1).`

### Explanation

```
:1reI                            § I is a number between 1 and Input
     lL,                         § L is the length of I
        "":Ic                    § Convert I to a string
             :.x                 § Remove all occurences of Output in that string
                l-L=%2=0,        § Check that the length of that new string - L mod 2 is 0
                         Iw,@Sw  § Write I, then write a space
                               \ § Backtrack (i.e. try a new value of I)

```

# Answer
> 2 votes
# Mathematica, 54 bytes

```
Position[Count[#2]/@IntegerDigits/@Range@#,x_/;2∣x]&

```

# Answer
> 2 votes
# Perl, 28 ~~29~~ ~~31~~ bytes

Includes +2 for `-an`

Run with the specification digit and count on consecutive lines on STDIN:

```
echo -e "0\n111" | perl -anE'map s/@F/$&/g%2||say,1..<>'

```

# Answer
> 2 votes
# Retina, ~~72~~ ~~71~~ 55

```
\d+$
$*
\B
¶$`
1+
$.0
G`(.),((?>.*?\1){2})*(?!.*\1)
.,
<empty>

```

Great thanks to Martin, who totally by accident reminded me of atomic matching groups!

Try it online!

### Explanation:

```
\d+$
$*

```

Replace the number, but not the digit, with its unary equivalent.

```
\B
¶$`

```

`\B` matches each position (zero-width) that is not a word boundary. Note that this will not match any of the following: the beginning of the string, the end of the string, or any position around the comma character. Each of these non-boundaries is then replaced with a newline and then the string that comes before the match (`$``). This gives a list like:

```
d,1
d,11
d,111

```

Where `d` is any single decimal digit.

```
1+
$.0

```

This converts all lists of `1`s into the decimal representation of their lengths. This conveniently won't affect the `1` that could be before the comma, as it's length it always `1` as well.

```
G`(.),((?>.*?\1){2})*(?!.*\1)

```

Here, the `G` turns on grep mode, which means that lines that match the regex are kept, and other lines are discarded. This regex is complicated, but it essentially matches groups of 2 of the leading digit (stored in capture group 1, so we can reference it with `\1`).

The key here, is that if it failed when using the non-greedy match up to the two earliest appearances of the digits, it would then just roll back and try again, with `.` matching over the digit. This would make numbers like 111 match when our digit is 1. Therefore, we use `?>` to make the match atomic, essentially preventing the regex from backtracking to before it matched this value. An atomic match works kind of like possesive matching would in certain flavours. Since the `*` meta-character is followed by a `?` the `.` will match characters up until it is able to match what we stored in `\1`. Then once we do this twice, the regular expression's "memory" is destroyed, preventing the behaviour that would normally occur, where it goes back and has the `.` match an additional character, our `\1` digit, which would created invalid matches.

Then, we check that from the final position, after matching repeated groups of two of the input digit, that we cannot match another input digit.

```
.,
<empty>

```

Here we are just removing the digit and comma from each of the strings, so we just get our nice answer.

# Answer
> 2 votes
# Java 8, 84 bytes

This is a lambda expression for a `BiConsumer< Integer, Integer>`:

```
(d,n)->for(int x=0;x++<n;)if((""+x).split(""+d,-1).length%2>0)System.out.println(x);

```

Explanation:

for each number between 1 and n, convert the number to a string and split it using d as the delimiter. If it was split into an odd number of sections, then print out the number followed by a new line.

# Answer
> 2 votes
# Oracle SQL 11.2, ~~111~~ 82 bytes

```
SELECT LEVEL FROM DUAL WHERE MOD(REGEXP_COUNT(LEVEL,:d),2)=0 CONNECT BY LEVEL<=:n;

```

# Answer
> 2 votes
## Kotlin, 136 bytes

```
fun main(a:Array<String>)=print({n:String,d:String->IntRange(1,n.toInt()).filter{"$it".count{"$it"==d}%2==0}.joinToString()}(a[0],a[1]))

```

Fully functional program, takes arguments as: n d

Try it online!

# Answer
> 1 votes
# Python 2, ~~57~~ 54 bytes

```
lambda d,n:[i for i in range(1,n+1)if`i`.count(d)%2<1]

```

---

### Usage

```
>>> (lambda d,n:[i for i in range(1,n+1)if`i`.count(d)%2<1])('1', 12)
[2, 3, 4, 5, 6, 7, 8, 9, 11]

```

# Answer
> 1 votes
# Julia, 44 bytes

```
f(n,d)=filter(i->sum(d.==digits(i))%2<1,1:n)

```

This is a function that accepts two integers and returns an array.

We start with the set of integers from 1 to `n`, inclusive. For each integer `i`, we determine which of its decimal digits are equal to `d`, which yields a Boolean array. We `sum` this to get the number of occurrences of `d` as a digit in `i`, and `filter` the original range based on the parity of the sum.

Try it here

# Answer
> 1 votes
## Seriously, 17 bytes

```
╩╜R;`$╛@c2@%Y`M@░

```

Takes inputs as `n\n'd'` (integer, newline, string).

Try it online!

Explanation:

```
╩╜R;`$╛@c2@%Y`M@░
╩                  push all inputs to registers
 ╜R;               push two copies of range(1, n+1)
    `        `M    map:
     $╛@c            count the number of d's
         2@%Y        modulo 2, logical not (1 if even, 0 if odd)
               @░  filter: take only the values of range(1, n+1) where the count is even

```

# Answer
> 1 votes
# Mathematica, 45 bytes

```
Select[a=#2;Range@#,2∣DigitCount[#,10,a]&]&

```

Uses the built-in `DigitCount`.

# Answer
> 1 votes
# Japt, ~~13~~ 12 bytes

```
Uò1 f_s èV v

```

Input is *n*, then *d* wrapped in quotes. **Test it online!**

### How it works

```
       // Implicit: U = input integer, V = input string
Uò1    // Create the inclusive range [1..U].
f_     // Filter to only the items Z that return truthily to this function:
s èV   //  Take Z.toString(), then count the number of matches of V.
v      //  Return 1 (truthy) if even, 0 (falsy) otherwise.
       // Implicit output, array separated by commas

```

# Answer
> 1 votes
# CJam, 38 bytes

```
r:P;r~1+,0-_{s{s}%Pe=2%!}%]z{~{}{;}?}%

```

---

### Explanation

```
r:P;                                    e# set input d to variable P
    r~1+,0-                             e# create a range(1, n+1)
           _{s{s}%Pe=2%!}%              e# determine which numbers are needed
                          ]z{~{}{;}?}%  e# remove extra numbers

```

# Answer
> 1 votes
# Scala, 66 bytes

```
(d:Int,n:Int)=>(1 to n).map(""+).filter(_.count((""+d)(0)==)%2==0)

```

# Answer
> 1 votes
# R, 145 bytes (I am sure there are ways to shorten this further) :)

```
g<-sapply(sprintf("%s",seq(1:111)),function(z){if(sapply(regmatches(z,gregexpr("0",z)),length)%%2==0){z}else{NULL}})
names(g[!sapply(g,is.null)])

```

# Answer
> 1 votes
# C, 175 Bytes

```
_;main(f,n,d){f?f-1?main(0,n,d),printf(_?"%d ":"",n),(n-1?main(2,n-1,d):0):(scanf("%d %d",&n,&d),main(2,n,d)):(n>9?n%10==d?(main(0,n/10,d),_=!_):main(0,n/10,d):(_=!(n==d)));}

```

Takes n, then d, from standard input. Prints the correct numbers in reverse order.

### Expansion

```
_; // declare return variable
main(f,n,d) //entry point (function selection [1==real main],n,d)
{
    f?
        f-1?
            //recursive loop from 'n' to 1
            main(0,n,d), //call even_digits?
            printf(_?"%d ":"",n),
            (n-1?main(2,n-1,d):0)
        :
            //actual main, just scan and run the loop
            (scanf("%d %d",&n,&d),main(2,n,d))
    :
        //even_digits? (stores result in _)
        (n>9? // recursive case, many digits
            n%10==d?
                (main(0,n/10,d),_=!_)
            :
                main(0,n/10,d)
         :
            (_=!(n==d)) //base case: 1 digit, return !(n==d)
        );
}

```

I feel like it might be possible to remove the duplicated `main(0,n/10,d)` near the end.

# Answer
> 1 votes
## Python 2, 68 chars

```
f=lambda d,n:filter(lambda x:x.count(`d`)%2^1,map(str,range(1,n+1)))

```

This function takes two ints and returns a list of the numbers with an even number of ds.

# Answer
> 1 votes
# Thunno 2, 5 bytes

```
æṘ¹cE

```

Try it online!

#### Explanation

```
æṘ¹cE  # Implicit input
æ      # Filter [1..first input] by:
   c   #   The count of...
  ¹    #   ...the second input...
 Ṙ     #   ...in this number...
    E  #   ...is even?
       # Implicit output

```

---
Tags: code-golf, integer
---


# Question
Title: Find the sum of all numbers below n that are a multiple of some set of numbers
Almost equivalent to Project Euler's first question:

> If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
>
> Find the sum of all the multiples of 3 or 5 below 1000.

## Challenge:

Given a positive integer `N` and a set of at least one positive integer `A`, output the sum of all positive integers less than `N` that are multiples of at least one member of `A`.

For example, for the Project Euler case, the input would be:

```
1000
3
5

```

## Test cases:

```
Input : 50, [2]
Output: 600

Input : 10, [3, 5]
Output: 23

Input : 28, [4, 2]
Output: 182

Input : 19, [7, 5]
Output: 51

Input : 50, [2, 3, 5]
Output: 857

```

# Answer
> 14 votes
# Jelly, 6 bytes

```
ḍþṖḅTS

```

Try it online!

### How it works

```
ḍþṖḅTS  Main link. Left argument: D (array). Right argument: n (integer)

ḍþ       Divisible table; test each k in [1, ..., n] for divisibility by all
        integers d in D.
  Ṗ     Pop; discard the last Boolean array, which corresponds to n.
   ḅ    Unbase; convert the Boolean arrays of base n to integer. This yields a
        non-zero value (truthy) and and only if the corresponding integer k is
        divisible by at least one d in D.
    T   Truth; yield the array of all indices of truthy elements.
     S  Compute their sum.

```

# Answer
> 9 votes
# Octave, ~~38~~ ~~36~~ 33 bytes

```
@(x,y)(1:--x)*~all(mod(1:x,y),1)'

```

Take input as: `f(10, [3;5])`. This would be 2 bytes shorter if the input could be `f(9,[3;5])` for the same test case.

Verify all test cases here.

---

**Explanation:**

```
@(x,y)        % Anonymous function that takes two inputs, x and y
              % x is a scalar and y is a vertical vector with the set of numbers
(1:--x)*      % Pre-decrement x and create a vector 1 2 ... x-1

```

Octave can pre-decrement, so using `1:--x` instead of `1:x-1` (two times) saves two bytes.

`mod(a,b)` gives `1 2 0 1 2 0 1 2 0` for `mod(1:9,3)`. If the second argument is a vertical vector, it will replicate the first input vertically and take the modulus for each of the values in the second input argument. So, for input `mod(1:9, [3;5])` this gives:

```
1 2 0 1 2 0 1 2 0
1 2 3 4 0 1 2 3 4

```

Taking `~all(_,1)` on this gives `true` for the columns where at least one value is zero, and `false` where all values are non-zero:

```
~all(mod(1:x,y),1)
0 0 1 0 1 1 0 0 1

```

The `,1` is needed in case there is only one number in `y`. Otherwise it would act on the entire vector instead of number-by-number.

Transposing this to a vertical matrix and use matrix multiplication, will give us the correct answer, without the need for explicit summing:

# Answer
> 8 votes
# Python, ~~59~~ 55 bytes

```
lambda n,l:sum(v*any(v%m<1for m in l)for v in range(n))

```

**repl.it**

Unnamed function taking an integer, `n` and a list of integers `l`. Traverses a range of the Natural numbers (plus zero) up to but not including `n` and sums (`sum(...)`) those that have a remainder after division of zero (`v%m<1`) for `any` of the integers `m` in the list `l`. Uses multiplication rather than a conditional to save 3 bytes.

# Answer
> 7 votes
## JavaScript (ES6), ~~40~~ ~~39~~ 36 bytes

Input: integer `n` and array of integer(s) `a` with currying syntax `(n)(a)`

```
n=>F=a=>n--&&!a.every(v=>n%v)*n+F(a)

```

### Test cases

```
let f =

n=>F=a=>n--&&!a.every(v=>n%v)*n+F(a)

console.log(f(50)([2]));        // 600
console.log(f(10)([3, 5]));     // 23
console.log(f(28)([4, 2]));     // 182
console.log(f(19)([7, 5]));     // 51
console.log(f(50)([2, 3, 5]));  // 857
```

# Answer
> 5 votes
# MATL, 9 bytes

```
q:ti\~*us

```

Try it online!

# Answer
> 5 votes
## Retina, 34 bytes

Byte count assumes ISO 8859-1 encoding.

```
\d+
$*
M&!`(.+)\1*(?=1¶.*\b\1\b)
1

```

Input format is

```
50
2,3,5

```

Try it online!

# Answer
> 4 votes
# Perl 6, 25 bytes

```
{sum grep *%%@_.any,^$^a}

```

A lambda that takes the input numbers as arguments. (One argument for N, and an arbitrary number of arguments for A).

(Try it online.)

### Explanation:

* `{ ... }`: A lambda.
* `$^a`: First argument of the lambda.
* `@_`: Remaining arguments of the lambda ("variadic parameter").
* `^$^a`: Range from `0` to `$^a - 1`.
* `* %% @_.any`: Another lambda, which tests its argument `*` using the divisible-by operator `%%` against an `any`-Junction of the list `@_`.
* `grep PREDICATE, RANGE`: iterates the range of numbers and returns the ones for which the predicate is true.

# Answer
> 4 votes
# Python, 67 bytes

```
a,b,c=input()
x=y=0
exec("if x%c<1or 1>x%b:y+=x\nx+=1\n"*a)
print y

```

After writing this I noticed my code was similar to the existing python answer, however I came up with it independently and am posting it anyway.

# Answer
> 4 votes
# Mathematica, ~~37~~ 27 bytes

*Thanks to Martin Ender for a shrewd observation that led to big byte savings!*

```
Tr[Union@@Range[#,#2-1,#]]&

```

Unnamed function taking two arguments, a list `#` of integers (the desired divisors `A`) and an integer `#2` (the upper bound `N`) , and returning an integer. `Range[#,#2-1,#]` gives, for each element `d` of the list `#`, all the multiples of `d` less than or equal to `#-1` (hence less than `#`); the union of these lists is then computed and summed with `Tr`.

Previous version:

```
Tr[x=#;Union@@(Range[#,x-1,#]&/@#2)]&

```

# Answer
> 4 votes
# R, 67 bytes

```
a=scan();x=c();for(i in a[-1])x=c(x,seq(i,a[1]-1,i));sum(unique(x))

```

Takes a vector to STDIN in the following format: `[N, a_1, a_2, ...]`. Supports any number of `a`. For each `a`, creates the sequence `a` to `N-1` with stepsize `a`. Then takes the sum of all the unique entries in that vector.

# Answer
> 3 votes
# Haskell, ~~42~~ 39 bytes

```
a!b=sum[x|x<-[1..a-1],any((<1).mod x)b]

```

Usage:

```
Main> 50![2,3,5]
857

```

Thanks to @Zgarb for 3 bytes

# Answer
> 3 votes
# Octave, ~~49~~ 37 bytes

```
@(A,N)sum(unique((z=(1:N)'.*A)(z<N)))

```

the function will be called as `f([2 3 4],50)`

Assume that `A=[2 3 4];` we require to have sum of numbers as

```
sum(
2,4,6...,50-1 ,
3,6,9...,50-1,
4,8,12,...50-1)

```

we can multiply `[2 3 4]` by `1:50` to get matrix `(1:N)'.*A`

```
[2 4 6 ... 2*50
3 6 9 ... 3*50
4 8 12 ...4*50]

```

then extract from the matrix those that are smaller than 50 : `z(z<N)`

Since there are repeated elements in the matrix we extract unique values and sum them.

**previous answer**: (this solution will fail if N==1)

```
@(A,N)sum((k=uint64(1:N-1))(any(k==(k./A').*A')))

```

function should be called as `f(unit64([2 3 4]),uint64(50))`

# Answer
> 3 votes
# 05AB1E, 9 bytes

```
FND²%P_*O

```

Try it online!

```
F         For N in [0, ..., input[0]-1]
 ND²%     Evaluate N%input[1]; yields an array of results
     P    Take the total product of the array. Yields 0 only if at least one of the value is 0, in other words if N is multiple of at least one of the specified values
      _   Boolean negation, yields 1 if the last value is 0 and yields 0 otherwise
       *  Multiply by N: yields N if the last value is 0 and yields 0 otherwise
        O Display the total sum

```

# Answer
> 3 votes
# Japt `-fx`, ~~9~~ ~~7~~ ~~6~~ 4 bytes

```
VøUâ

```

Try it

# Answer
> 3 votes
# Pip, ~~43 41 39~~ 35 bytes

```
b^:sFc,a{f:0Fdb{f?0c%d?0(f:i+:c)}}i

```

Try it online!

Explanation:

```
Takes inputs like so:

    arg1 1000
    arg2 3 5

b^:s                      ;read rest of inputs as array
                          ;(s is " " and ^ is split into array on char)
F c ,a{                   ;for(c in range(0,a))
  f:0                     ;flag to prevent double counting 15,30,etc.
  F d b {                 ;forEach(d in b)
    f? 0 c%d? 0 (f:i+:c)  ;if flag {continue}elif c%d {f=i+=c}
                          ;      (i will always be truthy so why not)
  }
}
i                         ;print sum

```

# Answer
> 2 votes
# Pyth, 10 bytes

```
s{sm:0hQdt

```

### Explanation

```
s{sm:0hQdtQ   Implicit input
    :0hQd     Get multiples of d below the bound
   m     tQ   ... for each d given
  s           Concatenate results
 {            Remove repeats
s             Take the sum

```

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

This will work as long as `@i` has a value of 2048 or lower

```
USE master--needed for databases not using master as default
DECLARE @i INT=50
DECLARE @ table(a int)
INSERT @ values(2),(3),(5)

SELECT sum(distinct number)FROM spt_values,@ WHERE number%a=0and abs(number)<@i

```

**Try it out**

# Answer
> 2 votes
## Ruby, ~~52 48~~ 46 bytes

```
->b{b[s=0].times{|x|b.find{|y|x%y<1&&s+=x}};s}

```

# Answer
> 2 votes
# APL (Dyalog Unicode), 12 bytes

```
+/⊢∘⍳∩∘∊×∘⍳¨

```

Try it online!

Anonymous tacit function. Thanks to @Adám for helping me shave 3 bytes off of this. Uses `⎕IO←0`.

### How:

```
+/⊢∘⍳∩∘∊×∘⍳¨ ⍝ Tacit function. Left and right arguments will be called ⍺ and ⍵ respectively.

        ×∘⍳¨ ⍝ Multiply ⍺ with each element of [0..⍵-1]
       ∊     ⍝ Enlist (flattens the vector)
     ∩∘      ⍝ Then, get the intersection of that vector with
  ⊢∘⍳        ⍝ The vector [0..⍵-1].
+/           ⍝ Then sum

```

# Answer
> 2 votes
# Google Sheets, ~~141 140 134 132~~ 90

Closing parens already discounted.

Phew! That was more work than I bargained for. The hard part was getting something that worked for all ranges.

### Inputs:

* `A1` \- N
* Row `2` \- A1, A2, ...

### Formulae:

* `A3` \- `=A1-1` (N - 1)
* `A4` \- `=SUM(ArrayFormula(SEQUENCE(A3)*LT(,COUNTIF(MMULT(SEQUENCE(A1),FILTER(2:2,2:2)),SEQUENCE(A3)))))`

Where `A4` is the final output.

### How It Works

Hint: Start from the middle.

```
# Sum everything together
=SUM(
    ArrayFormula(
        # The "number under N"
        SEQUENCE(A3)*
        # Use the LT Operator function to pile parens at the end
        LT(
            # Implicit 0
            ,
            COUNTIF(
                # Generate every multiple of each element in A via matrix multiplication up to the Nth multiple.
                # This is overkill, but saves characters.
                MMULT(
                    # Column Matrix `(1, ... , N)` and Row Matrix `(A1, A2, ...)`.
                    SEQUENCE(A1),
                    # Have to remove blanks from the end
                    FILTER(2:2,2:2)
                ),
                # If element appears in the resulting matrix, multiply by 1, or else 0
                SEQUENCE(A3)
            )
        )
    )
)

```

# Answer
> 2 votes
# x86-16 machine code, ~~27~~ 25 bytes

Binary:

```
00000000: 33db 4a51 56ac a20c 018a c2d4 0ae0 f675  3.JQV..........u
00000010: 0203 da5e 594a 75eb c3                   ...^YJu..

```

Listing:

```
33 DB       XOR  BX, BX                 ; clear BX running sum
4A          DEC  DX                     ; N = N - 1 (only multiples below N)
        N_LOOP:
51          PUSH CX                     ; save array length
56          PUSH SI                     ; save array start pointer
        F_LOOP:
AC          LODSB                       ; AL = next factor
A2 0C01     MOV  BYTE PTR[AAM1+1], AL   ; AAM divisor = AL
8A C2       MOV  AL, DL                 ; AL = dividend
        AAM1:
D4 0A       AAM                         ; ZF = ( current N % factor == 0 )
E0 F6       LOOPNZ F_LOOP               ; if not a multiple, continue to next factor
75 02       JNZ  F_BREAK                ; if last is not a multiple, don't add
03 DA       ADD  BX, DX                 ; otherwise add factor to sum
        F_BREAK:
5E          POP  SI                     ; restore array pointer
59          POP  CX                     ; restore array length
4A          DEC  DX                     ; decrement N / loop counter
75 EB       JNZ  N_LOOP                 ; loop until N = 0
C3          RET                         ; return to caller

```

As a function: input `N` in `DL`, `SI` array of factors, `CX` array size.

Once again, using DOS DEBUG to test. Note: literal values are in hex in DEBUG.

`N` = `10` (`0xA`), `[ 3, 5 ]` = `23` (`0x17`)

`N` = `50` (`0x32`), `[ 2, 3, 5 ]` = `857` (`0x359`)

# Answer
> 2 votes
# Fig, \\$11\log\_{256}(96)\approx\\$ 9.054 bytes

```
VxSFrx'!A%v

```

*-8.232 bytes thanks to @Sʨɠɠan*

Try it online!

Explanation:

```
Vx           # Set the register to the first input (the list)
    rx       # Range [0, n)
   F  '      # Filter:
         %   #   Modulo
          v  #   The register
        A    #   All truthy
       !     #   Logical not
  S          # Sum

```

# Answer
> 2 votes
# Pyt, 9 bytes

```
⁻řĐ←ΠǤ1>·

```

Try it online!

```
⁻ř            implicit input (N); decrement and push [1,2,...,N-1]
  Đ           duplicate top of stack
   ←Π         get the product of the members of A
     Ǥ        GCD (elementwise)
      1>      is each GCD greater than 1?
        ·     dot product; implicit print

```

# Answer
> 2 votes
# Nekomata, 7 bytes

```
ᵒ%ᵐ∏¬x∙

```

Attempt This Online!

```
ᵒ%ᵐ∏¬x∙
ᵒ%          Generate a modulo table
  ᵐ∏        Take product of each row
    ¬       Logical not
     x∙     Dot product with range from 0 to length - 1

```

# Answer
> 2 votes
# Itr, 13 bytes

`#º#Xáà%¬*«ÍÌS`

online interpreter

# Explanation

```
#              ; read the number
 º             ; convert it to a zero-based range
  #            ; read the list of numbers
   ×     «     ; execute for each pair of numbers in the input
    áà         ; duplicate the lower number in the pair
      %¬       ; check for divisibility
        *      ; keep the number if it is divisible
         ÍÌ    ; uniquify the list
           S   ; sum up the elements

```

---

# Itr, 11 bytes

using implicit IO

`ºXâà%¬*«ÍÌS`

# Answer
> 2 votes
# Rust, 52 bytes

```
|n,v|(1..n).filter(|e|v.iter().any(|x|e%x==0)).sum()

```

Rust Playground

# Answer
> 1 votes
## Python 2, 80 Bytes

This is very long. Can definitely be shortened. Taking the 3 numbers as separate inputs is definitely hurting the score.

```
i=input
x=i();y=i();z=i();s=c=0
exec("if c%z<1 or c%y<1:s+=c\nc+=1\n"*x)
print s

```

# Answer
> 1 votes
# Actually, 13 bytes

```
DR∙`i;)%Y*`MΣ

```

Try it online!

Explanation:

```
DR∙`i;)%Y*`MΣ
DR             range(1, N)
  ∙            Cartesian product with A
   `i;)%Y*`M   for each pair:
    i;)          flatten, make a copy of the value from the range
       %Y        test if value from range divides value from A
         *       value from range if above is true else 0
            Σ  sum

```

# Answer
> 1 votes
## Common Lisp, 77

```
(lambda(n x)(loop for i below n when(some(lambda(u)(zerop(mod i u)))x)sum i))

```

### Ungolfed

```
(lambda (limit seeds)
  (loop for i below limit
        when (some (lambda (u) (zerop (mod i u))) seeds)
          sum i))

```

# Answer
> 1 votes
# PowerShell, 57 bytes

```
param($a,$b)(1..--$a|?{$i=$_;$b|?{!($i%$_)}})-join'+'|iex

```

Try it online!

Iterative solution. Takes input as a number `$a` and as a literal array `$b`. Loops from `1` up to one below `$a` (via `--$a`), using a `Where-Object` operator `|?{...}` with a clause to select certain numbers.

The clause sets `$i` to be the current number before sending input array `$b` into another `|?{...}`, here picking out those items where the current number is evenly divided by at least one of the numbers in `$b`. Those elements of `$b` that do divide evenly are left on the pipeline.

Thus, if there is at least one element from `$b`, the pipeline contains an element, so the outer `Where` is `$true` and the current number is left on the pipeline. Otherwise, with no elements from `$b` on the pipeline, the outer `Where` is `$false`, so the current number is not placed on the pipeline.

Those numbers are all gathered up in parens, `-join`ed together with `+` signs, and piped to `|iex` (short for `Invoke-Expression` and similar to `eval`). The summation result is left on the pipeline, and output is implicit.

# Answer
> 1 votes
# PHP, ~~78~~ ~~76~~ 74 bytes

```
for(;++$i<$argv[$f=$k=1];$s+=$i*!$f)for(;$v=$argv[++$k];)$f*=$i%$v;echo$s;

```

The outer loop runs `$i` from 1 to below first argument and adds `$i` to `$s` if `$f` is *not* set.
The inner loop multiplies `$f` with (`$i` modulo argument) for all subsequent arguments, setting `$f` to `0` if `$i` is the multiple of any of them.

Run with `-r`.

# Answer
> 1 votes
# Scala, 47 bytes

```
n=>1.to(n(0)-1).filter(i=>n.exists(i%_==0)).sum

```

n is a List which contains of a first argument `N`, the rest are elements of `A`

Works by filtering out numbers where there doesn't exist at least one A of which i is a multiple, then summing. Strictly speaking we should use `n.tail.exists` inside the closure, but as i is always less than N and therefore never a multiple of N the solution is still complete without this.

# Answer
> 1 votes
# Java 8, 75 bytes

```
(N,A)->IntStream.range(1,N).filter(x->A.stream().anyMatch(y->x%y==0)).sum()

```

The method signature for this is `int f(int N, List<Integer> A)`

# Answer
> 1 votes
# C11, 177 bytes

```
#include"object.h"
#define S size_t
S g(S m,array_t*d){S s,i,l,j;for(s=i=0;i<m;i++){for(l=1,j=0;j<d->idx+1;l*=i%(S)(*array_get_ref(d,j++,NULL))->fwi->value);s+=l?0:i;}return s;}

```

Requires this set of headers in the same folder, and the `fnv-hash` library found there as well. Compile like `gcc 1.c ../fnv-hash/libfnv.a -o 1 -DNODEBUG`

Test Program:

```
#include "../calc/object/object.h"
#include <stdio.h>

size_t f (const size_t max, const size_t a, const size_t b);
size_t f2 (const size_t max, const array_t* const divs);
size_t g (size_t max, array_t* divs);

define_array_new_fromctype(size_t);

int main(void) {
  printf("%zu\n", f(10, 3, 5));
  static const size_t a[] = {
    3, 5
  };
  array_t* b = array_new_from_size_t_lit(a, 2, t_realuint);
  printf("%zu\n", f2(10, b));
  printf("%zu\n", g(10, b));
  array_destruct(b);
  return 0;
}

size_t f (const size_t max, const size_t a, const size_t b) {
  size_t sum = 0;
  for (size_t i = 0; i < max; i++) {
    sum += (i % a * i % b) ? 0 : i;
  }
  return sum;
}

size_t f2 (const size_t max, const array_t* const divs) {
  size_t sum = 0;
  const size_t len = array_length(divs);

  for (size_t i = 0; i < max; i++) {
    size_t mul = 1;
    for (size_t j = 0; j < len; j++) {
      object_t** this = array_get_ref(divs, j, NULL);

      fixwid_t*   num = (*this)->fwi;

      mul *= i % (size_t) num->value;
    }
    sum += mul ? 0 : i;
  }
  return sum;
}

#define S size_t
S g(S m,array_t*d){S s,i,l,j;for(s=i=0;i<m;i++){for(l=1,j=0;j<d->idx+1;l*=i%(S)(*array_get_ref(d,j++,NULL))->fwi->value);s+=l?0:i;}return s;}

```

outputs

```
23
23
23

```

# Answer
> 1 votes
# Whispers v2, 178 bytes

```
> Input
> Input
> ℕ
>> (1)
>> ∤L
>> {L}
>> L∩2
>> #L
>> L∈3
>> L⋅R
>> Each 5 4
>> Each 6 11
>> Each 7 12
>> Each 8 13
>> Each 9 14
>> Each 10 15 4
>> ∑16
>> Output 17

```

Try it online!

Structure tree:

## How it works

Very simply, we put each number (the lines with `Each` on them) through a series of functions (the lines with `L` on them), then, based off the results of those functions, we discard some numbers and keep the rest, before finally summing them. In fact, we can define those functions, where \\$\alpha\\$ denotes the set of numbers given as input:

\begin{align} f(x) & = \\{i \\: | \\: (i|x), i \in \mathbb{N}\\} & \text{i.e. the set of divisors of} \\: x \\ g(x) & = f(x) \cup \alpha & \text{i.e. the union of the divisors of} \\: x \\: \text{with} \\: \alpha \\ h(x) & = |g(x)| \> 0 & \text{i.e.} \\: g(x) \\: \text{is not empty} \end{align}

This is what lines **5** through to **10** represent. Lines **11** through **16** are simply the application of those three functions. Once we've defined all the functions, we then mutate \\$\alpha\\$ to \\$\beta\\$ according to the following rule:

$$\beta\_i = \begin{cases} \alpha\_i & h(\alpha\_i) \\: \top \\ 0 & h(\alpha\_i) \\: \bot \end{cases}$$

where \\$\alpha\_i\\$ denotes the \\$i\\$th element of \\$\alpha\\$, and the same for \\$\beta\\$. Finally, we can simply take the sum of \\$\beta\\$, as the \\$0\\$ elements do not affect the sum.

# Answer
> 1 votes
# K (oK), ~~15~~ 14 bytes

**Solution:**

```
{+/&|/~y!\:!x}

```

Try it online!

**Examples:**

```
{+/&|/~y!\:!x}[50;,2]
600
{+/&|/~y!\:!x}[10;3 5]
23

```

**Explanation:**

```
{+/&|/~y!\:!x} / the solution
{            } / lambda taking implicit x and y
           !x  / range 0..x-1
       y!\:    / modulo (!) x with each-left (\:) item in y
      ~        / not
    |/         / min-over to flatten into single list
   &           / indices where true
 +/            / sum up

```

# Answer
> 1 votes
# Pip, 12 bytes

```
$+Y0N_%gFI,q

```

Try it online!

### Explanation

Uses a somewhat unusual input method: takes N from stdin and the set of divisors as command-line args.

```
$+Y0N_%gFI,q
              g is list of command-line args (implicit)
           q  Read a line of stdin
          ,   Range from 0 up to one less than that value
        FI    Filter on this function:
     _         Take each element
      %g       mod the list of divisors g
   0N          Check if zero is in the result list: some number in g divides the element exactly
              Result: a list of the numbers that are a multiple of one of the set of divisors
  Y           Yank (no-op to manipulate operator precedence)
$+            Fold on addition

```

# Answer
> 1 votes
# Io, 63 bytes

Port of NikoNyrh's answer.

```
method(N,A,A map(i,Range 0toBy(N-1,i)asList)flatten unique sum)

```

Try it online!

## Explanation

```
method(N,A,                                                   ) // Take two inputs, the number and the array
           A map(i,                        )                    // For each item in the array A:
                   Range 0toBy(N-1,i)                           //     Generate a range from 0 to N-1, with the step of i
                                     asList                     //     Convert it to a list
                                            flatten             // Flatten the lists
                                                    unique      // Uniquify them
                                                           sum  // Sum the resulting list

```

# Answer
> 1 votes
# Scala, ~~45~~ 41 bytes

```
s=>0 to _-1 filter(x=>s.exists(x%_<1))sum

```

Try it in Scastie

Takes as its input a `List[Int]` `s` and an `Int`, creates a range from 0 to that number, filters every number in that range that's divisible by an element in `s`, and sums it.

Requires `language:postfixOps`.

# Answer
> 1 votes
# Arn, 15 bytes

```
pIÔX╗▀‹·¬○¯vËa?

```

# Explained

Unpacked: `+\$v{$:{!v%}?1}1->`

```
  \ Fold with...
+ ...addition
    $ Filter with...
      v{ ...block with key of v
        $: Any operation
          { Block with key of _
            ! Boolean not
              v% v modulo _ (implied)
          }
          ?1 Each element on second line of _ (implied)
        }
        1-> Range, [1, _)

```

When passing an array in string or integer context, Arn will automatically take the 0th element. When passing a string/integer in array context, Arn will split on spaces if there are any or every character otherwise.

STDIN is initialized to the **_** variable, split on newlines if there are any or just a string if one line.

Originally I had `+\$v{$:{0=v%}?1}1->`, which was 1 byte longer.

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

```
ɽ'⁰Ḋa

```

Try it online!

Explanation:

```
ɽ      # Range 1 to n-1
 '     # Keep those that are
   Ḋ   #   Divisible by
    a  #   Any of
  ⁰    #   The second input
       # Sum with the s flag

```

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

```
Læ¹ḊS

```

Try it online!

## Thunno 2 `S`, 6 bytes

```
LsȷḊʂV

```

Try it online!

#### Explanations

```
Læ¹ḊS   # Implicit input           ->  [2,3,5], 50
L       # Lowered range            ->  [2,3,5], [0..49]
 æ      # Filtered by:             ->     0       1    ...   48      49
  ¹Ḋ    #  Divisible by 2nd input  ->  [1,1,1] [0,0,0]     [1,1,0] [0,0,0]
    S   #  Sum (any are true)      ->     3       0    ...    2       0
        # (End filter)             ->  [0,2,3,4,5,...,42,44,45,46,48]
        # (S flag) Sum the list    ->  857
        # Implicit output

```

```
LsȷḊʂV  # Implicit input
        #   [2,3,5], 50
L       # Take the lowered range of the first input
        #   [2,3,5], [0..49]
 s      # Swap the two values on the stack
        #   [0..49], [2,3,5]
  ȷḊ    # Outer product over divisibility check
        #   [[0%2==0, 0%3==0, 0%5==0], ..., [49%2==0, 49%3==0, 49%5==0]]
        #   [[1,1,1], [0,0,0], [1,0,0], ..., [0,0,0], [1,1,0], [0,0,0]]
    ʂ   # Sum each inner list (check if any are true)
        #   [3,0,1,1,1,...,2,1,0,2,0]
     V  # Get the indices of truthy (non-zero) items
        #   [0,2,3,4,5,...,42,44,45,46,48]
        # (S flag) Sum the resulting list
        #   857
        # Implicit output

```

# Answer
> 1 votes
# Julia 1.0, 31 bytes

```
N^A=sum(x->any(@.x%A<1)x,1:N-1)

```

Try it online!

The function `sum` can accept a subfunction to be called on each element before summation. I use this to multiply each element `x` in the range \\$\[1, N-1\]\\$ by the boolean value `any(@.x%A<1)`, essentially filtering the range. Julia supports logical indexing for arrays, but this generally requires defining the array first, which often isn't ideal for code golf.

The expression `@.` vectorizes the functions that follow, but in this case, it doesn't save any bytes over the alternative, `x.%A.<1`.

-1 byte thanks to MarcMush: use the result of `any` as a literal coefficient

# Answer
> 0 votes
# Processing, 88 bytes

```
int q(int a,int[]b){int s=0,i=0;for(;++i<a;)for(int j:b)if(i%j<1){s+=i;break;}return s;}

```

Uses the simple `for`-loop approach, sums all the multiples up and returns it. Input is the format `int`, `int[]`array.

# Answer
> 0 votes
# , 18 bytes

```
[:+/@I.0=*/@(|/i.)

```

Try it online!

## Explanation

```
[:+/@I.0=*/@(|/i.)  Input: A (LHS), N (RHS)
               i.   Make the range [0, 1, ..., n-1]
             |/     Form the modulus table between each value in A and the range N
         */@(    )  Reduce columns by multiplication
       0=           Test if each value if equal to 0, 1 if true else 0
[:   I.             Find the indicies of 1s
  +/@               Reduce by addition and return

```

# Answer
> 0 votes
# PHP, 80 bytes

```
for($c=1;++$i<$argv[1];$c++?:$t+=$i)for($j=1;$v=$argv[++$j];$i%$v?:$c=0);echo$t;

```

Run from command line with `-r`. First argument is the limit `N`, any subsequent arguments are our positive integers `A`.

Our outer loop goes through the range `1..N`, while the inner loop goes through each value of `A` and checks to see if `$i` is a multiple of it. If it is, we set a flag that tells our outer loop to add `$i` to our total (`$t`). We use a flag so that we don't add `$i` more than once. We then output our total at the end.

# Answer
> 0 votes
## R, 39 bytes

```
z=2:N-1;z%*%!!rowSums(!outer(z,X,"%%"))

```

`N` is the number, `X` is a vector of divisors

# Answer
> 0 votes
**Clojure, 44 bytes**

```
#(apply +(set(mapcat(partial range 0 %)%2)))

```

Instead of generating the whole range form 0 to N it is generating values on that range with step length of A\_0, A\_1, etc. and uses `set` to get unique values.

Calling convention:

```
(def f #(apply +(set(mapcat(partial range 0 %)%2))))
(f 50 [2 3 5])

```

Steps are more clear when `->>` macro is used:

```
(defn f [N A] (->> A (mapcat #(range 0 N %)) set (apply +)))

```

# Answer
> 0 votes
**Python 3 & 2.7, 55 bytes**

Based on the same `set` idea as my Clojure version.

```
lambda N,A:sum(set(i for a in A for i in range(0,N,a)))

```

# Answer
> 0 votes
## Batch, 110 bytes

```
@set t=-%1
@for /l %%i in (1,1,%1)do @set p=1&(for %%e in (%*)do @set/ap*=%%e%%%%i)&set/at+=%%i*!p
@echo %t%

```

Takes input as command-line arguments; the first argument is `n`, the rest are the set of numbers. Works by computing the product of the remainders of all numbers up to and including `n` with each of the arguments including `n` itself and summing those numbers with a zero product; this causes `n` to always be included in the total so we offset that by starting the total at `-n`.

# Answer
> 0 votes
# C#, 92 bytes

```
n=>{int i=0,j,s=0;for(;i<n[0];i++)for(j=1;j<n.Length;)if(i%n[j++]<1){s+=i;break;}return s;};

```

Anonymous function which receives an array containing the upper limit and all required divisors.

This method does not use a set (actually HashSet in C#) since it was way too verbose. Not that this code is too succinct...

Full program and test cases:

```
using System;

public class Program
{
    public static void Main()
    {
        Func<int[], int> f =
        n =>
        {
            int i = 0, j, s = 0;
            for ( ; i < n[0] ; i++)
                for (j = 1 ; j < n.Length ; )
                    if (i % n[j++] < 1)
                    {
                        s += i;
                        break;
                    }
            return s;
        };

        // test cases:
        Console.WriteLine(f(new int[]{50, 2})); // 600
        Console.WriteLine(f(new int[]{10, 3, 5}));  // 23
        Console.WriteLine(f(new int[]{28, 4, 2}));  // 182
        Console.WriteLine(f(new int[]{19, 7, 5}));  // 51
        Console.WriteLine(f(new int[]{50, 2, 3, 5}));   // 857
    }
}

```

# Answer
> 0 votes
## awk, 64 bytes

```
{for(;i++<NF;j=0)while((c=$i*++j)&&c<$NF)a[c];for(i in a)$0+=i}1

```

Write the code to file `program.awk` and execute:

```
$ echo run 2 3 5 50 | awk -f this.awk
857

```

`run` is a cludge to allow using record `$0` for summing and shorter printing, emphasis on the latter.

Try it online

# Answer
> 0 votes
## Racket 94 bytes

```
(apply +(remove-duplicates(for*/list((i(range 1(car l)))(j(cdr l))#:when(= 0(modulo i j)))i)))

```

Ungolfed:

```
(define (f l)
  (apply +
         (remove-duplicates
          (for*/list
              ((i (range 1 (first l)))
               (j (rest l))
               #:when (= 0 (modulo i j)))
            i))))

```

Testing:

```
(f '(10 3 5))
(f '(50 2))
(f '(28 4 2))
(f '(19 7 5))
(f '(50 2 3 5))

```

Output:

```
23
600
182
51
857

```

# Answer
> 0 votes
# APL(NARS), 17 chars, 34 bytes

```
{+/∪⍺∼⍨∊⍵×⍳¨⌊⍺÷⍵}

```

test:

```
  f←{+/∪⍺∼⍨∊⍵×⍳¨⌊⍺÷⍵}
  50 f 2
600
  10 f 3 5
23
  28 f 4 2
182
  19 f 7 5
51
  50 f 2 3 5
857

```

# Answer
> 0 votes
# Perl 5 `-pa`, 44 bytes

```
map{$"="*$_%";$\+=!eval"$_%@F"&&$_}1..<>-1}{

```

Try it online!

Takes the list of `A` on the first line of input, space separated. Takes `N` on the second line.

# Answer
> 0 votes
# Headass, 74 bytes

```
{N)OUO}:+E.UO^UO[{UON)}:](D)RP:N+E.U+O-[UOU{R)U-ORO^:R-OUO;UN)}:D)R:R];ONE

```

Try It Online! \- Input is taken as a newline delimited list of numbers, with the first one being `N`, and the rest being the values of `A`

tattoo on my forehead that says `I LOVE EASY CHALLENGES`

## Explanation

```
PREAMBLE: this program counts up from 0 to N, with this increasing value being
referred to as the "counter". along the way it reads members of A, which
will be given "countdown timers", which start at 0 and are reset to the
associated A member value minus one, so that every A[i]th cycle, they reach
0 and trigger the adding of the counter to the accumulator.
The accumulator, of course, accumulatizes.

{N)OUO}:+E.  code block 0 (initialization)
{N)   }:     for each input
   OUO         save 0, save input
               this inits the counter, stores N,
               creates a list of countdown timers starting at 0
               and implicitly, an accumulator starting at 0
               all on the queue. the queue now looks like this:
               0 N 0 A1 0 A2 0 A3... 0
        +E   go to code block 1
          .  end code block

UO^UO[{UON)}:](D)RP:N+E.  code block 1 (checking if we're done)
UO^                       set r1 to the counter value
   UO[                    set r2 to N
      {UON)}:             put the rest of the values back on the queue,
                          noting that the accumulator is the last value
             ](D)         if r1 == r2 (the counter has reached N)
                 RP         print the last value added to the queue
                            (which is the accumulator)
                            (and halt)
                   :      else
                    N+E     go to code block 2
                       .  end code block

U+O-[UOU{R)U-ORO^:R-OUO;UN)}:D)R:R];ONE  code block 2
U+O                                      put the counter + 1 onto the queue
U+ -[                                    set r2 to the counter value
     UO                                  put N back on the queue
        {                N)}:            for each member of A
       U R)             U                  if the countdown timer has reached 0
           U-O                               reset the countdown timer
              RO                             put the A member back on the queue
                ^                            raise a flag in r1
                 :                         else
                  R-O                        decrement the countdown timer
                     UO                      put the A member back on the queue
                       ;                   endif
                             D)          if the flag in r1 is down
                               R:  ;O      put the accumulator back on the queue
                                :        else
                                 R];O      increase the accumulator by the
                                           value of the counter
                                     NE  return to code block 1

```

There's a bunch of implicit re-adding of values to the queue that I don't mention, basically any time I say that I've modified some value, that means I'm saving the modified version to the queue.

Also, registers r0-r3 are reset between code blocks, so you can basically think about them as local variables in each code block. Register r0 is constantly in use but not mentioned due to the language structure, and register r3 is in use whenever `(` or `)` show up, but it's much easier to abstract these to simple comparisons, since that's all they're used for in this program.

I'm still always learning the best way to explain this language, trying to balance between overexplaining and overabstracting, if anyone has any questions of course feel free to ask, you may have a golf on your hands :P

---
Tags: code-golf, math, number, integer
---


# Question
Title: Computing a specific coefficient in a product of polynomials
## Generator functions

*This gives the context for why this challenge came to life. Feel free to ignore.*

Generator functions are a nice way of encoding the solution to a problem of combinatorics. You just write some polynomials, multiply them and then your solution is the coefficient of one of the terms.

For example, how many bouquets of 10 flowers can you make if you want to use 3 or more dandelions, really want to use an even number of lilies and cannot afford more than 5 roses? Easy, just find the coefficient of `x^10` in

$$(x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^{10})\times(1 + x^2 + x^4 + x^6 + x^8 + x^{10})\times(1 + x + x^2 + x^3 + x^4 + x^5)$$

## Task

Compute a specific coefficient from a product of polynomials.

## Example

If `k = 3` and the product given is `"(1 + 3x + 5x^2)(5 + 3x + 2x^2)"` then we have

$$(1 + 3x + 5x^2)(5 + 3x + 2x^2) = (5 + 3x + 2x^2) + (15x + 9x^2 + 6x^3) + (25x^2 + 15x^3 + 10x^4) = 5 + 18x + 36x^2 + 21x^3 + 10x^4$$

And because `k = 3` we get 21.

## Input

You receive an integer `k` and several polynomials. `k` is always a non-negative integer, and so are the coefficients and the exponents in the input polynomials.

`k` may be larger than the combined degree of all the input polynomials.

The input polynomials can be in any sensible format. A few suggestions come to mind:

* A string, like `"(1 + 3x + 5x^2)(5 + 3x + 2x^2)"`
* A list of strings, like `["1 + 3x + 5x^2", "5 + 3x + 2x^2"]`
* A list of lists of coefficients where index encodes exponent, like `[[1, 3, 5], [5, 3, 2]]`
* A list of lists of `(coefficient, exponent)` pairs, like `[[(1, 0), (3, 1), (5, 2)], [(5, 0), (3, 1), (2, 2)]]`

An input format must be sensible AND completely unambiguous over the input space.

## Test cases

```
0, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 5
1, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 18
2, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 36
3, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 21
4, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 10
5, "(1 + 3x + 5x^2)(5 + 3x + 2x^2)" -> 0
6, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 8
7, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 0
8, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 32
9, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 0
17, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 0
18, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 160
19, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 0
20, "(1 + 2x^2 + 4x^4)(2x^2 + 4x^4 + 8x^8)(4x^4 + 8x^8 + 16x^16)" -> 384

```

# Answer
> 10 votes
# , ~~21~~ ~~19~~ 18 bytes

```
{ ::0[:+//.@(*/)/>

```

Try it online!

*-1 byte thanks to FrownyFrog*

J has a nice geometric idiom for multiplying polynomials, which we represent as lists of coefficients, with explicit zeroes where needed:

```
+//.@(*/)

```

Let's see how this works using the example:

```
1 3 5 +//.@(*/) 5 3 2

```

First it creates a multiplication table `*/`:

```
 5  3  2
15  9  6
25 15 10

```

And `@:` then it computes the sums along each diagonal `+//.` using the Oblique `/.` adverb:

This works because moving down a diagonal is equivalent to decrementing the power of one *x* while incrementing the power of another, meaning that the numbers along a diagonal represent all the components of some a factor `x^n` for some `n`.

The rest of the solution is just mechanics for the problem as stated:

```
{ ::0[: <polynomial idiom> />

```

Since we can have an arbitrary number of polynomials, we represent them as a list of boxes (each box containing one polynomial) and take that as the right arg. The left arg is the index we want.

Now `{ ::0 ...` is a dyadic hook asking for the index specified by the left arg, after transforming the right arg by everything in `...`. And, if you can't find the index, return 0 `::0`.

Finally `[: <polynomial idiom> />` says to first unbox `>` the right arg lists, filling any missing coefficients with 0. Then reduce `/` that list using the polynomial multiplication idiom.

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

```
Y:iWB1G"Y+]2GQ)

```

Input is a cell array of numerical vectors with the polynomial coefficients, followed by an integer (`k`).

Try it online! Or verify all test cases.

### Explanation

Polynomial multiplication is convolution of their coefficients. And

> convolution is the key to success

```
Y:     % Implicit input: cell array of numeric vectors. Unbox into its constituents
iWB    % Input k. 2 raised to that. Convert to binary. Gives [1 0...0] with k zeros
1G     % Push first input (cell array of numeric vectors) again
"      % For each. This runs n iterations, where n is the number of polynomials
  Y+   %   Convolution
]      % End
       % The first convolution uses one of the polynomials in the input and the
       % [1 0...0] vector. This doesn't alter the actual coefficients, but adds k
       % zeros. Thus the final product polynomial will contain k zeros after the
       % highest-degree nonzero coefficient. This ensures that k doesn't exceed
       % the number of existing coefficients
2G     % Push second input (k) again
Q      % Add 1
)      % Index. This retrieves the k-th degree coefficient. Implicit display

```

# Answer
> 6 votes
# Haskell, 42 bytes

```
n%((h:t):l)=h*n%l+(n-1)%(t:l)
0%[]=1
_%_=0

```

Try it online!

An infix function taking a number `n` and a lists of lists of coefficients with lowest exponents first.

Here's the key recursive idea. Instead of actually multiplying out the polynomials to get one big polynomial, we only just try to extract the coefficient. Algorithmically, this isn't faster than multiplying out coefficient, but in terms of brevity, it saves us from needing to product lists for the intermediate or final product.

When multiply \\$p(x)\cdot q(x)\\$, we can split up \\$p(x)\\$ into its constant and remaining terms as \\$p(x)=p\_0(x) +x \cdot p\_{\mathrm{rest}}(x)\\$. Then, the coefficient of \\$x^n\\$ in \\$p(x)\cdot q(x)\\$ can be written as:

$$ \begin{align} \[p(x)\cdot q(x)\]\_n &= \[(p\_0 +x \cdot p\_{\mathrm{rest}}(x)) \cdot q(x)\]\_n \\ &= \[p\_0 \cdot q(x)\]\_n + \[x \cdot p\_{\mathrm{rest}}(x) \cdot q(x)\]\_n \\ &= p\_0 \cdot q(x)\_n + \[p\_{\mathrm{rest}}(x) \cdot q(x)\]\_{n-1} \\ \end{align} $$

We can continue expanding this out recursively until we get \\$p=0\\$, where the remaining result is zero. If \\$q(x)\\$ is itself expressed as a product of polynomials, we continue to extract coefficients from there. The base case is that the empty product is \\$1\\$, so its \\$x^0\\$ coefficient is \\$1\\$ and the rest are zero.

# Answer
> 5 votes
# Mathematica, 20 bytes

A nice benchmark for other answers:

```
Coefficient[#2,x,#]&

```

Takes the symbolic expressions as input.

You can try it online!

# Answer
> 5 votes
# Jelly,  ~~22 17~~  7 bytes

-10 bytes by realising I'd implemented convolution - go upvote Luis Mendo's MATL answer too, as that was what made me realise this.

```
æc/ṫ‘}Ḣ

```

A dyadic link accepting a list of coefficient lists on the left and the exponent on the right.

**Try it online!** Or see the test suite.

### How?

```
æc/ṫ‘}Ḣ - Link: list of lists, Ps; integer, E
  /     - reduce (Ps) by:
æc      -   convolution
     }  - use right argument (E) for:
    ‘   -   increment -> E+1
   ṫ    - tail from (1-indexed) index (E+1)
      Ḣ - head (if given an empty list yields 0)

```

---

The 17 (without the convolution atom) was:

```
×€Œd§ṙLC${Ṛð/ṫ‘}Ḣ

```

# Answer
> 5 votes
# Python, 67 bytes

```
f=lambda n,p,*q:p>[]and(f(n,*q)if q else n==0)*p[0]+f(n-1,p[1:],*q)

```

Try it online!

Takes input like `f(3,[1,2,3],[4,5,6])`, with the polynomials as separate arguments. The idea for the recursion if the same as in my Haskell answer. But, since Python doesn't have as nice pattern matching, we need to check for empty lists explicitly.

# Answer
> 3 votes
# Husk, ~~18~~ 16 bytes

```
!→⁰+→G(mΣ∂Ṫ*)²∞0

```

First Husk answer. This took so much longer to complete than I thought it would. I'm glad there is a tutorial with good explanation of how the input-order and super-numbers work, otherwise I had to give up. I never programmed in Haskell, and maybe I'm just too used to the left-to-right stack-based 05AB1E, but Husk isn't exactly straight-forward due to its strong-typed nature and right-to-left execution (including input-arguments) imho..
But, it works, which is what counts in the end. :)

First input-argument is a list of lists of coefficients where index encodes exponent, like the third input example in the challenge description. Second argument is the coefficient integer \\$k\\$.

Try it online.

**Explanation:**

```
             ²    # Use the first argument,
     G(     )     # and left-reduce it by:
          Ṫ       #  Apply double-vectorized:
           *      #   Multiply
                  #  (This basically results in the multiplication table of the lists)
         ∂        #  Take the diagonals of this multiplication table
       m          #  Map over these diagonal-lists:
        Σ         #   And sum each together
    →             # Only leave the last list after the reduce-by
              ∞0  # Push an infinite list of 0s: [0,0,0,...]
   +              # Merge the two lists together
  ⁰               # Push the second argument `k`
 →                # Increase it by 1 (since Husk uses 1-based indexing instead of 0-based)
!                 # And use it to index into the list we created
                  # (after which the result is output implicitly)

```

# Answer
> 2 votes
# Python 2, ~~139~~ 131 bytes

```
lambda k,L:sum(reduce(lambda a,(i,c):a*c[i],zip(p,L),1)for p in product(*map(range,map(len,L)))if sum(p)==k)
from itertools import*

```

Try it online!

Takes as inputs `k` and then polynomials as a list of lists of coefficents `[c0, c1, c2, ...]`. Forms all tuples of indexes into the polynomials that sum to the desired coefficent; and then sums up the products of the corresponding coefficients.

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

```
f=(k,[p,...t],s=0)=>p?p.map((n,i)=>s+=f(k-i,t)*n)&&s:!k

```

Try it online!

The first argument is `k`. The second argument is "a list of lists of coefficients where index encodes exponent", like `[[1, 3, 5], [5, 3, 2]]`.

# Answer
> 2 votes
# Jelly, ~~19~~ 15 bytes

```
×þŒJ§SƙFƲ¥/ṫ‘}Ḣ

```

Try it online!

A dyadic link taking `k` as the left argument and the list of polynomials as a list of lists of coefficients as the right argument. Returns an integer. If `k` could be 1-indexed, `‘}` could be deleted for 13 bytes.

Adapted to use @JonathanAllan’s revised method for dealing with larger `k`; be sure to upvote his (still shorter) answer too!

# Answer
> 2 votes
# 05AB1E, ~~32~~ ~~24~~ 23 bytes

```
Å»δ*εā_«N(._}øO}θIÅ0«Iè

```

Definitely not the right language to use for this challenge (no builtins for convolution, polynomials, getting all diagonals of a matrix, etc.).. But with some -rather long- workarounds, it still works (although is too slow for the last test cases).

Input as a list of list of coefficients where index encodes exponent, as well as the integer \\$k\\$ as second input.

Inspired by *@Jonah*'s J answer.
-8 bytes by porting two approaches I've used in my Husk answer.

Try it online or verify some more test cases (outputs all coefficients without the indexing part).

**Explanation:**

```
Å»        # Left reduce the (implicit) input-list of lists of integers by:
          #  1) Calculate the multiplication table of the current two lists:
  δ       #   Apply double-vectorized:
   *      #    Multiply
          #  2) Take the sums of each diagonal:
  ε       #   Map each inner list to:
   ā      #    Push a list in the range [1,list-length] (without popping the list itself)
    _     #    Convert each to 0, so we'll have a list of 0s of the same length
     «    #    Append this list of 0s to the current list
      NF  #    Loop the 0-based map-index amount of times:
        Á #     And rotate the current list that many times towards the right
  }}      #   End the loop and map
    ø     #   Zip/transpose; swapping rows/columns
          #   (We now have a list of all diagonals)
     O    #   And take the sum of each inner list
}θ        # After the reduce-by is done, pop and push the final resulting list
  ∞_«     # Append an infinite amount of trailing 0s
     Iè   # And then use the second input to (0-based) index into this list
          # (after which the result is output implicitly)

```

# Answer
> 2 votes
# , 68 bytes

```
function(P,k)Re(Reduce(function(x,y)convolve(x,y,,"o"),P,!0:k)[k+1])

```

Try it online!

Convolution is the key to success here, too, since it's a port of Luis' answer.

Takes input as a `list()` of vectors `c()` of coefficients in *decreasing* order, because R's convolve documentation says:

> Note that the usual definition of convolution of two sequences `x` and `y` is given by `convolve(x, rev(y), type = "o")`.

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

```
f(k,p)=polcoeff(vecprod(p),k)

```

Try it online!

# Answer
> 2 votes
# Sledgehammer, 6 bytes

```
⣈⠲⡎⡒⢢⣑

```

Only works in the interactive app (that requires excessive amounts of tinkering to get it to actually decompress the Braille code itself, but it's possible), because of a bug where the console app doesn't call `postprocess` and ends up replacing all occurrences of `#, #1, #2, ##` by `s1, s2, s3, ss1`.

Accepts input as, for example, `{"(1 + 2x1^2 + 4x1^4)(2x1^2 + 4x1^4 + 8x1^8)(4x1^4 + 8x1^8 + 16x1^16)", 20}` \- `x1` is the variable the first undefined variable used gets replaced with.

Obtained from the Mathematica code `Coefficient[ToExpression@#, z, #2]` (where `ToExpression` is `eval` and `Coefficient` simply gets the right coefficient, and `z` gets replaced by `x1` as part of the compression).

# Answer
> 2 votes
# Itr, 9 bytes

`#RC*µS«#@`

Input: nonempty list of polynomials (given as coefficient vectors) followed by index of coefficient that should be computed

Does not work if input list is empty

online interpreter

## Explanation

```
#          ; read the list of polynomials
 R     «   ; reduce with
  C*µS     ; polynomial multiplication
  C*       ; go through the diagonals of the Cartesian product, multiplying the two elements in the pairs
    µS     ; sum up the diagonals
        #@ ; get the specified coefficient
           ; implicit output

```

---

# Itr, 10 bytes

Also works for empty input list

`1#MC*µS«#@`

Input: list of polynomials (given as coefficient vectors) followed by index of coefficient that should be computed

## Explanation

```
1           ; push 1
 #          ; read the list of polynomials
  M     «   ; for polynomial in the list
   C*µS     ; multiply that polynomial with the top stack value
         #@ ; get the specified coefficient
            ; implicit output

```

---

# ~~Itr, 8 bytes~~ (only works for 2 inputs)

`##C*µS#@`

Input: two list of coefficients for the polynomials followed by the index of the coefficents

online interpreter

## Explanation

```
##       ; read the two coefficient lists for standard input
  C*µS   ; multiply them as polynomials
  C*     ; go through the diagonals of the Cartesian product, multiplying the two elements in the pairs
    µS   ; sum up the diagonals
      #@ ; get int specified coefficient
         ; implicit output

```

# Answer
> 2 votes
# K (ngn/k), 39 bytes

```
{0^({.+/'(*/x@'i)@=+/i:!#'x:(x;y)}/y)x}

```

Try it online!

# Answer
> 1 votes
# Charcoal, 52 bytes

```
≔⟦Ｅ²ι⟧ζＦη«≔⟦⟧υＦιＦζ⊞υＥκ⎇ν×μ§λ¹⁺μ§λ⁰≔υζ»Ｉ∨ΣＥΦυ⁼§ι⁰θ⊟ι⁰

```

Try it online! Link is to verbose version of code. Takes input using the last suggestion but with the exponent first, then the coefficient. Explanation:

```
≔⟦Ｅ²ι⟧ζ

```

Initialise a variable to the polynomial `1`.

```
Ｆη«

```

Loop over the input polynomials.

```
≔⟦⟧υ

```

Accumulate terms in a temporary variable.

```
ＦιＦζ

```

Loop over the Cartesian product of both sets of terms.

```
⊞υＥκ⎇ν×μ§λ¹⁺μ§λ⁰

```

Multiply the coefficients and add the exponents.

```
≔υζ

```

Move the resulting terms back to the original variable. (Charcoal doesn't have any flattening operators, and this is the golfiest way of flattening manually.)

```
»Ｉ∨ΣＥΦυ⁼§ι⁰θ⊟ι⁰

```

Filter for the terms with the desired exponent and sum the coefficients, unless there weren't any, in which case the result is `0`.

# Answer
> 1 votes
# Brachylog, 16 bytes

```
⟨∋ᵐ{tᵐ+}⟩ᶠhᵐ²×ᵐ+

```

Try it online!

Takes input as a list of lists of `[coefficient, exponent]` pairs, paired with `k`. Could be trivially modified to accept index-as-exponent coefficient lists by replacing  with `i`, which is in fact what I did originally before I made an error writing out the test cases and switched for my own convenience.

```
⟨       ⟩           Call the first element of the input L and the last element k.
         ᶠ          Find every
 ∋                  selection of a [coefficient, exponent] pair
  ᵐ                 from each polynomial in L
   {   }            such that k is
      +             the sum of
    tᵐ              the exponents.
          hᵐ²       Extract the coefficients from each selection,
             ×ᵐ     multiply the coefficients extracted from each selection,
               +    and output the sum of the products.

```

`{⟨∋ᵐ{tᵐ+}⟩hᵐ×}ᶠ+` is an equally valid solution at the same length, but I'm not sure I remember ever superscripting  before this, so I'm just going with the version that does that.

---
Tags: code-golf, math, integer, combinatorics, polynomials
---


title: Multiply multivariate polynomials

text:
# Question
Title: Multiply multivariate polynomials
*We already have a challenge about multiplying multiply single-variable polynomials. This challenge is about multiply two polynomials with multiple variables*

Your task is given two multi-variable polynomials (for instance given as nested lists) to return their product.

## Examples

```
(x²+x+1)*(x²+x+1)=x⁴+2x³+3x²+2x+1
(x+y)*(x+y)=x²+2xy+y²
(x+y+z)*(x-y+z) = x²-y²+2xz +z²
a*a=a²

```

when representing polynomials as nested lists1:

```
[1,1,1], [1,1,1]                                     -> [1, 2, 3, 2, 1]
[[0,1],[1]], [[0,1],[1]]                             -> [[0, 0, 1], [0, 2], [1]]
[[[0,1],[1]],[[1]]], [[[0,1],[-1]],[[1]]]            -> [[[0, 0, 1], [0], [-1]], [[0, 2]], [[1]]]
[[],[[[[[[[[[1]]]]]]]]]], [[],[[[[[[[[[1]]]]]]]]]] -> [[], [], [[[[[[[[[1]]]]]]]]]]

```

(non-golfed) solution in Python

## Rules

* You can Input/Output the polynomials in any convenient format (as long as each output can only represent one polynomial)
* Input and Output have to use the same format for polynomials
* You can assume that all coefficients are integers
* If you take input as lists you can assume that all numbers in both inputs appear in the nesting depth
* You are allowed to omit zero coefficients in the output (as long as the output value are unambiguous)
* You can use the empty list to represent zero/the zero polynomial
* If your language has a built-in for multi-variable polynomial multiplication consider adding a non-built-in solution as well
* This is the shortest solution wins

---

1short explanation of the nested list format used in the examples (you are free to use a different IO format):

Each list represents a single variable polynomial with its coefficients begin either integers or other lists representing polynomials in one less variable. The coefficients are multiplied with the polynomial variable to the power of their index:

```
[[[0,1],[1]],[[1]]] -> "[[0,1],[1]]"*1+"[[1]]"*z -> ("[0,1]"*1+"[1]"*y)*1+"[1]"*1*z -> (x*1+1*y)*1+1*1*z -> x+y+z

```

The variables are assigned by nesting layer. I use `x` for the innermost variable `y` for the next level, then `z`.

# Answer
> 3 votes
# JavaScript (Node.js), 80 bytes

```
f=(x,y,s=[])=>x>f&&x.map((p,i)=>y.map(q=>f(p,q,s[i++]||=[])||(s[i-1]-=-p*q)))&&s

```

Attempt This Online!

# JavaScript (Node.js), 84 bytes

```
f=(x,y,s=[])=>x>f&&x.map((p,i)=>y.map(q=>f(p,q,s[i]=s[i++]||[])||(s[i-1]-=-p*q)))&&s

```

Try it online!

# Answer
> 3 votes
# Charcoal, ~~115~~ 112 bytes

```
ＦＥθ⟦⟦ι⟧⟧«Ｗ⁺⟦⟧§§ι⁰±¹≔ΣＥιＥ⊟λ⁺λ⟦ξν⟧ι⊞υι»≔⟦⟧θＦ⊟υ«≔⊟ιηＦ⌊υ«≔Ｅι⁺λ§κμζ≔⊟ζε≔θδＦζ≔§⎇⁼λＬδ⊞Ｏδ⟦⟧δλδＦ⁼εＬδ⊞δ⁰§≔δε⁺§δε×↨κ⁰η»»⭆¹θ

```

Attempt This Online! Link is to verbose version of code. Explanation: Charcoal doesn't really like multidimensional indexing. I should really find time to test this out on my multidimensional indexing branch to see whether it offers a significant saving.

```
ＦＥθ⟦⟦ι⟧⟧«

```

Double wrap each input polynomial and then loop over them.

```
Ｗ⁺⟦⟧§§ι⁰±¹≔ΣＥιＥ⊟λ⁺λ⟦ξν⟧ι

```

Replace each polynomial with a list of its elements and their multidimensional indices.

```
⊞υι

```

Save the resulting list.

```
»≔⟦⟧θ

```

Start building up the output list.

```
Ｆ⊟υ«

```

Loop over the second polynomial's multidimensional index list.

```
≔⊟ιη

```

Remove the coefficient from the multidimensional index.

```
Ｆ⌊υ«

```

Loop over the first polynomial's multidimensional index list.

```
≔Ｅι⁺λ§κμζ

```

Get the multidimensional index of the product of the two terms.

```
≔⊟ζε

```

Remove the innermost index.

```
≔θδ

```

Start traversing the dimensions of the output list.

```
Ｆζ

```

Loop over the earlier multidimensional indices.

```
≔§⎇⁼λＬδ⊞Ｏδ⟦⟧δλδ

```

Get the inner list at the current multidimensional index, extending the current list if necessary.

```
Ｆ⁼εＬδ⊞δ⁰

```

Extend the innermost list if necessary.

```
§≔δε⁺§δε×↨κ⁰η

```

Add on the resulting coefficient to the element at the innermost index.

```
»»⭆¹θ

```

Pretty-print the resulting list.

# Answer
> 3 votes
# K (ngn/k), 60 55 bytes

```
{(.p),','!p:+/'(*p)@=*|p:(*/;+/)@''++',/,/:\:/,''(x;y)}

```

Try it online!

-5 : Save a lambda

Here multinomials are represented by lists of terms where each term is a pair of coefficients and list of powers of each variable in reverse order.

Thus,

```
(x-y+z) -> [[[1,[0,0,1]],[-1,[0,1,0]],[1,[0,0,1]]]

```

or in K notation:

```
((1;0 0 1)
 (-1;0 1 0)
 (1;1 0 0))

```

Cleaning up terms with zero coefficients is left to an auxiliary function.

# Answer
> 2 votes
# Python3, 490 bytes:

```
def U(p,l=1,o=1):
 if type(p)!=list or[]==p:yield(p if p!=[]else 0,o);return
 for i,a in enumerate(p):yield from U(a,l+1,{l:i}if o==1 else{**o,l:o.get(l,0)+i})
def G(p,l=1):
 r={}
 for c,D in p:
  if l in D:r[V]=r.get(V:=D.pop(l),[])+[(c,D)]
 return[G(r[i],l+1)if i in r else 0 for i in range(max(r)+1)]if r else c
def M(a,b):
 r={}
 for c,p in U(a):
  for C,P in U(b):r[K]=r.get(K:=str({**p,**{A:p.get(A,0)+B for A,B in P.items()}}),0)+c*C
 return G([(b,eval(a))for a,b in r.items() if b])

```

Try it online!

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

```
Expand[1##]&

```

Try it online. The inevitable built-in. `1##` multiplies together all arguments to a function, regardless of the types of those objects. (So this function works for more than two polynomials as well.)

---
Tags: code-golf, polynomials, ragged-list
---


title: Zeckendorf to F(4k+2) representation

text:
# Question
Title: Zeckendorf to F(4k+2) representation
## Background

Fibonacci numbers are defined as follows:

$$ F\_0 = 0, F\_1 = 1, F\_n = F\_{n-1} + F\_{n-2} $$

The **Zeckendorf representation** is a representation of positive integers as a sum of one or more non-adjacent Fibonacci numbers, using indices 2 and higher. It is known that such a representation is unique for every positive integer (Zeckendorf's theorem), and it can be written as a positional base system using digits 0 and 1. For example:

$$ 65 = 55 + 8 + 2 = F\_{10} + F\_{6} + F\_{3} = \overline{100010010}\_F $$

The **\\$F\_{4k+2}\\$ representation** is a similar representation but using every fourth Fibonacci number only, and with digits of at most 9. Some examples:

$$ \begin{align} 7 &= 7F\_2 = \overline{7}\_{F\_{4k+2}} \\ 8 &= 8F\_2 = \overline{8}\_{F\_{4k+2}} \\ &= F\_6 = \overline{10}\_{F\_{4k+2}} \\ 65 &= F\_{10} + F\_6 + 2F\_2 = \overline{112}\_{F\_{4k+2}} \\ \end{align} $$

Note that this representation is not unique in general.

I invented this to multiply two numbers in Zeckendorf representation in subquadratic time, from the fact that the product of two \\$F\_{4k+2}\\$s can be expanded to a sum of \\$F\_{4k+2}\\$s:

$$ \begin{align} F\_2 F\_n &= F\_n \\ F\_6 F\_n &= F\_{n-4} + F\_n + F\_{n+4} \\ F\_{10} F\_n &= F\_{n-8} + F\_{n-4} + F\_n + F\_{n+4} + F\_{n+8} \\ &\cdots \\ F\_{4k+2} F\_n &= \sum\_{i=-k}^{k} F\_{n+4i} \end{align} $$

## Task

Given a positive integer in Zeckendorf representation, output the same number in \\$F\_{4k+2}\\$ representation. If there are multiple possible representations, output any of them.

Both the input and output may be represented using a list or string of digits, in the order of increasing or decreasing positional value. For example, if the given number is `11`, you may choose to take e.g. `"10100"`, `"00101"`, `[1, 0, 1, 0, 0]`, or `[0, 0, 1, 0, 1]` as input, and give `"13"`, `"31"`, `[1, 3]`, or `[3, 1]` as output.

## Test cases

```
Number Zeckendorf      F4k+2 (not showing all possible answers)
7      1010            7
10     10010           12
12     10101           14
51     10100101        63
144    10000000000     242
233    100000000000    415
490    1001001000100   1203 or 1172 or 862
986    10101010101010  2414

```

# Answer
# JavaScript (ES6), 88 bytes

Expects a binary array in reverse order. Returns an array which may include leading 0's.

```
a=>a.reduce((q,c,i)=>(t+=c*=x=y+(y=x),i&3?q:[x,...q]),[],t=y=0,x=1).map(x=>t/(t%=x,x)|0)

```

Try it online!

### How?

We have two steps:

1. During the `reduce()` step, we convert the input array \\$a\[\\:\]\\$ of length \\$L\\$ into an integer \\$t\\$ by computing Fibonacci numbers \\$F\_2\\$ to \\$F\_{L+1}\\$ and adding those for which the corresponding entry in \\$a\[\\:\]\\$ is set. At the same time, we store the Fibonacci numbers of the form \\$F\_{4k+2}\\$ in this range in an array \\$q\[\\:\]\\$, from highest to lowest.
2. During the `map()` step, we convert \\$q\[\\:\]\\$ into the final output by computing \\$\lfloor t/x\rfloor\\$ for each entry \\$x\\$ and reducing \\$t\\$ modulo \\$x\\$ after each iteration.

### Commented

```
a =>                     // a[] = input array
a.reduce((q, c, i) =>    // for each value c at index i in a[],
  (                      // using q[] as the accumulator:
    t +=                 //   add to t ...
      c *=               //     c multiplied by ...
        x = y + (y = x), //       the next Fibonacci number x
    i & 3 ?              //   if i is not a multiple of 4:
      q                  //     leave q[] unchanged
    :                    //   else:
      [x, ...q]          //     append x at the beginning of q[]
  ),                     //
  [],                    //   start with q = []
  t = y = 0,             //   start with t = 0, y = 0
  x = 1                  //   start with x = 1
)                        // end of reduce()
.map(x =>                // for each value x in q[]:
  t / (t %= x, x)        //   return floor(t / x)
  | 0                    //   and reduce t modulo x
)                        // end of map()

```
> 3 votes

# Answer
# 05AB1E, ~~21~~ 19 bytes

```
ƶ+ÅfODÅF4ι2èRvy‰`s?

```

Try it online, or try all test cases

-2 thanks to @Kevin Cruijssen

Takes the input as a reversed list. Turns the number from Zeckendorf representation to an integer, and then finds an \\$F\_{4k+2}\\$ representation greedily.

## Explanation

```
ƶ      multiply each number by its 1-based index
+      and add that to the original list, so effectively we multiplied by the 2-based index
Åf     get the n-th Fibonacci number, for each N in that list
O      and sum, let's call it V
D      duplicate
ÅF     list the fibonacci numbers less than or equal to it
4ι     uninterleave to four lists [a[0::4], a[1::4], a[2::4], a[3::4]]
2è     and take the third element, a[2::4]
R      reverse that list
v      and for each element in the list:
 y      push it
 ‰      calculate divmod(V, element)
 `      dump (division, mod)  to the stack
 s      swap, to get (mod, division)
 ?      and print the result of the division without a newline, leaving the modulo in the stack in place of V.

```
> 2 votes

# Answer
# Charcoal, 41 bytes

```
Ｆθ⊞υ∨¬υΣ…⮌υ²≔ΣＥ⮌θ×Ｉι§υκθＦ⮌Φυ¬﹪κ⁴«Ｉ÷θι≧﹪ιθ

```

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

```
Ｆθ⊞υ∨¬υΣ…⮌υ²

```

Generate `F(2)...F(n+1)` where `n` is the number of bits in the input.

```
≔ΣＥ⮌θ×Ｉι§υκθ

```

Convert the input from Zeckendorf to integer.

```
Ｆ⮌Φυ¬﹪κ⁴«Ｉ÷θι≧﹪ιθ

```

Greedily convert the input from integer to `F(4k+2)`.
> 2 votes

# Answer
# Python, 150 bytes

```
def f(i):
 a=b=g=1;o=0
 def n(o):
  while(z:=(o+g-1)//8&g):o-=o//8%2-(z*145>>4)
  return o
 while i:o=n(o+i%2*b);a,b=b,n(a+b);i//=2;g=16*g+1
 return o

```

Attempt This Online!

Expects binary coded Zeckendorf and returns hex coded F4k+2.

## How?

Uses the identity \\$7F\_n= F\_{n-4}+F\_{n+4}\\$ to express addition in F4k+2 using "two-sided carry".
> 1 votes

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