Mod-balanced lists

Question

Introduction

Suppose I have a list of integers, say L = [-1,2,2,1,2,7,1,4]. I like having balance in my life, so I'm happy to see it has as many odd elements as even elements. What's more, it also has an equal number of elements in all modulo classes of 3 that it has elements in:

         [-1,2,2,1,2,7,1,4]
0 mod 3:
1 mod 3:         1   7 1 4
2 mod 3:  -1 2 2   2

Sadly, for the modulo classes of 4 this no longer holds. In general, we say a non-empty list is balanced modulo N if it has an equal number of elements in all modulo classes of N for which this number is not 0. The above list L is balanced modulo 2 and 3, but unbalanced modulo 4.

The task

Your input is a non-empty list L of integers taken in any reasonable format. Your output is the list of those integers N ≥ 2 such that L is balanced modulo N, again in any reasonable format. The order of the output does not matter, but it should not contain duplicates.

It is guaranteed that there are only finitely many numbers in the output, which means precisely that not all elements of L occur an equal number of times in it. Examples of invalid inputs are [3], [1,2] and [0,4,4,0,3,3]. Notice that the largest number in the output is at most max(L) - min(L).

The lowest byte count in each language wins, and standard code-golf rules apply.

Test cases

[1,1,2] -> []
[1,1,5] -> [2,4]
[1,1,24] -> [23]
[1,2,3,2] -> [2]
[12,12,-4,20] -> [2,3,4,6,8,12,24]
[1,1,12,12,-3,7] -> [3,10]
[-1,2,2,1,2,7,1,4] -> [2,3]
[4,-17,-14,-18,-18,3,5,8] -> []
[-18,0,-6,20,-13,-13,-19,13] -> [2,4,19]
[-11,-19,-19,3,10,-17,13,7,-5,16,-20,20] -> []
[3,0,1,5,3,-6,-16,-20,10,-6,-11,11] -> [2,4]
[-18,-20,14,13,12,-3,14,6,7,-19,17,19] -> [2,3]
[-16,-9,6,13,0,-17,-5,1,-12,-4,-16,-4] -> [3,9]
[-97,-144,3,53,73,23,37,81,-104,41,-125,70,0,111,-88,-2,25,-112,54,-76,136,-39,-138,22,56,-137,-40,41,-141,-126] -> [2,3,6]

Answer 1

Wolfram Language (Mathematica), 56 52 bytes

Thanks to Not a tree for saving 4 bytes.

Cases[Range[2,#.#],n_/;Equal@@Last/@Tally[#~Mod~n]]&

Try it online!

The main golfing trick is to use the sum of absolute values (or the 1-norm) sum of squared values, computed as a dot product with itself, as the upper bound instead of Max@#-Min@#. Otherwise, it just implements the spec very literally.

Answer 2

05AB1E, 11 bytes

ÄOL¦ʒ%{γ€gË

Try it online!

ÄOL¦ʒ%{γ€gË  | Full program.

Ä            | Absolute value (element-wise).
 O           | Sum.
  L          | 1-based inclusive range.
   ¦         | Remove the first element (generates the range [2 ... ^^]).
    ʒ        | Filter / Select.
     %       | Modulo of the input with the current integer (element-wise).
      {      | Sort.
       γ     | Group into runs of adjacent elements.
        €g   | Get the length of each.
          Ë  | Are all equal?

Answer 3

Haskell, 85 84 bytes

f l=[n|n<-[2..sum$abs<$>l],all.(==)=<<head$[r|m<-[0..n],_:r<-[[0|x<-l,mod x n==m]]]]

Try it online! Uses the sum of absolute values as maximum from Martin Ender's answer.

Edit: -1 byte thanks to Ørjan Johansen.

Explanation:

f l=                             -- Given a list of numbers l,
  [n|n<-                       ] -- return a list of all numbers n of the range
    [2..sum$abs<$>l],            -- from 2 to the sum of the absolute values of l
      all.(==)=<<head$           -- for which all elements of the following list are equal:
        [r|m<-[0..n],         ]  -- A list r for each number m from 0 to n, where
          _:r<-[             ]   -- r is the tail of a list (to filter out empty lists)
          [0|x<-l,mod x n==m]    -- of as many zeros as elements of l mod n equal m.

Answer 4

Perl 6,  52  48 bytes

{grep {[==] .classify(*X%$^a).values},2.. .max-.min}

Test it

{grep {[==] bag($_ X%$^a).values},2.. .max-.min}

Test it

Expanded:

{  # bare block lambda with implicit parameter ｢$_｣

  grep

    {  # bare block lambda with placeholder parameter ｢$a｣

      [==]           # reduce with &infix:«==» (are the counts equal to each other)

        bag(         # group moduluses together

          $_ X% $^a  # find all the moduluses using the current divisor ｢$a｣

        ).values     # the count of each of the moduluses
    },

    2 .. .max - .min # all possible divisors
}

Answer 5

Husk, 13 bytes

f₅⁰…2ṁa⁰
Λ≈k%

Try it online!

Answer 6

R, 75 72 bytes

function(L){for(x in 2:(max(L)-min(L)))F=c(F,!sd(table(L%%x)))
which(F)}

Try it online!

Uses table to compute the counts of each integer modulo x. The standard deviation sd of a set of numbers is zero iff they are all equal, and positive otherwise. Hence !sd(table(L%%x)) is TRUE wherever L is mod-balanced mod x and false otherwise. These values are then concatenated into F.

which then returns the indices of true values from the function. Since R uses 1-based indexing and F is initially a length-one vector with value FALSE, this will correctly return values beginning with 2.

One might expect the builtin function range to compute the range of a dataset, i.e., max(D)-min(D), but sadly it computes and returns the vector c(min(D), max(D)).

Answer 7

Clean, 121 bytes

Uses the sum-of-absolutes trick from Martin Ender's answer.

Golfed:

import StdEnv   
f l=[n\\n<-[2..sum(map abs l)]|length(removeDup[length[m\\m<-[(e rem n+n)rem n\\e<-l]|m==c]\\c<-[0..n]])<3]

Readable:

import StdEnv
maximum_modulus l = sum (map abs l)
// mod, then add the base, then mod again (to fix issues with negative numbers)
list_modulus l n = [((el rem n) + n) rem n \\ el <- l]
// count the number of elements with each mod equivalency
equiv_class_count l n = [length [m \\ m <- list_modulus l n | m == c] \\ c <- [0..n]]
// for every modulus, take where there are only two quantities of mod class members
f l=[n \\ n <- [2..maximum_modulus l] | length (removeDup (equiv_class_count l n)) < 3]

Try it online!

Answer 8

Jelly, 12 bytes

⁹%LƙE
ASḊçÐf

Try it online!

Thanks to user202729 for saving a byte and to Martin Ender (indirectly) for saving a byte.

How it works

⁹%LƙE ~ Helper link. Let's call the argument N.

⁹%    ~ Modulo the input by N (element-wise).
  Lƙ  ~ Map with length over groups formed by consecutive elements.
    E ~ All equal?

ASḊçÐf ~ Main link.

AS     ~ Absolute value of each, sum.
  Ḋ    ~ Dequeue (create the range [2 ... ^]).
   çÐf ~ Filter by the last link called dyadically.

A one-liner alternative 12-byter can be tried online!

Answer 9

Python 3, 120 102 bytes

Not pretty golfy.

-18 bytes thanks to Mr. Xcoder.

f=lambda a,i=2:[]if i>max(a)-min(a)else(len({*map([k%i for k in a].count,range(i)),0})<3)*[i]+f(a,i+1)

Try it online!

Answer 10

MATL, 19 bytes

-4 bytes thanks to Luis Mendo!

S5L)d:Q"G@\8#uZs~?@

Try it online!

Port of my answer in R.

Suppose we have input [12,12,-4,20]
         # (implicit input), stack: [12,12,-4,20]
S        # sort the list, stack: [-4, 12, 12, 20]
5L       # push [1 0], stack: [[-4, 12, 12, 20]; [1 0]]
)        # 1-based modular index, stack: [-4, 20]
d        # successive differences, stack: [24]
:        # generate 1:(max(data)-min(data)), stack: [[1...24]]
Q        # increment to start at 2, stack: [[2...25]]
"        # for each element in [2...25]
 G       # push input, stack: [[12,12,-4,20]]
 @       # push loop index, stack: [[12,12,-4,20], 2]
 \       # compute modulo, stack: [[0,0,0,0]]
 8#      # use alternate output spec, unique has 4 outputs, so 8 keeps only the 4th
 u       # unique. 4th output is the counts of each unique value, stack: [4]
 Zs      # compute standard deviation, stack: [0]
 ~       # logical negate, stack: [T]
 ?       # if true,
  @      # push loop index
         # (implicit end of if)
         # (implicit end of for loop)
         # (implicit output of stack as column vector

Answer 11

APL (Dyalog), 43 41 38 30 bytes

The ⍨s in the code tells the whole story.

8 bytes saved thanks to @Adám

∊x⊆⍨1=⊂(≢∘∪1⊥|∘.=|)¨⍨x←1+∘⍳1⊥|

Try it online!

Answer 12

JavaScript (ES6), 117 bytes

Outputs a space-separated list of values.

a=>(g=m=>a.map(n=>x[k=(z|=m/2<n|m/2<-n,n%m+m)%m]=-~x[k],y=z=0,x=[])|z?(x.some(x=>x-(y?y:y=x))?'':m+' ')+g(m+1):'')(2)

Test cases

let f =

a=>(g=m=>a.map(n=>x[k=(z|=m/2<n|m/2<-n,n%m+m)%m]=-~x[k],y=z=0,x=[])|z?(x.some(x=>x-(y?y:y=x))?'':m+' ')+g(m+1):'')(2)

console.log(f([1,1,2])) // []
console.log(f([1,1,5])) // [2,4]
console.log(f([1,1,24])) // [23]
console.log(f([1,2,3,2])) // [2]
console.log(f([12,12,-4,20])) // [2,3,4,6,8,12,24]
console.log(f([1,1,12,12,-3,7])) // [3,10]
console.log(f([-1,2,2,1,2,7,1,4])) // [2,3]
console.log(f([4,-17,-14,-18,-18,3,5,8])) // []
console.log(f([-18,0,-6,20,-13,-13,-19,13])) // [2,4,19]
console.log(f([-11,-19,-19,3,10,-17,13,7,-5,16,-20,20])) // []
console.log(f([3,0,1,5,3,-6,-16,-20,10,-6,-11,11])) // [2,4]
console.log(f([-18,-20,14,13,12,-3,14,6,7,-19,17,19])) // [2,3]
console.log(f([-16,-9,6,13,0,-17,-5,1,-12,-4,-16,-4])) // [3,9]
console.log(f([-97,-144,3,53,73,23,37,81,-104,41,-125,70,0,111,-88,-2,25,-112,54,-76,136,-39,-138,22,56,-137,-40,41,-141,-126])) // [2,3,6]

Answer 13

Clojure, 91 bytes

#(for[i(range 2(apply +(map * % %))):when(apply =(vals(frequencies(for[j %](mod j i)))))]i)

Using frequencies isn't ideal in code golf.

Answer 14

J, 38 bytes

[:}.@I.([:i.1#.|)(1=1#.[:~:|#/.])"0 1]

Credit goes to Mr. Xcoder for the sum of absolute values trick.

Edit in a TIO link if you want -- I've golfed this in a bit of a hurry.

Explanation and TIO link coming soon(ish).