# Knödel numbers - Find Kn

The Knödel numbers are a set of sequences. Specifically, the Knödel numbers for a positive integer $$\n\$$ are the set of composite numbers $$\m\$$, such that all $$\i < m\$$, coprime to $$\m\$$, satisfy $$\i^{(m-n)} \equiv 1 \mod m\$$. The set of Knödel numbers for a specific $$\n\$$ is denoted $$\K_n\$$. (Wikipedia).

For example, $$\K_1\$$ are the Carmichael numbers, and OEIS A002997. They go like: $$\\{561, 1105, 1729, 2465, 2821, 6601, ... \}\$$. $$\K_2\$$ is OEIS A050990 and goes like, $$\\{4, 6, 8, 10, 12, 14, 22, 24, 26, ... \}\$$.

Your task is to write a program/function/etc. that takes two numbers, $$\n\$$ and $$\p\$$. It should return the first $$\p\$$ numbers of the Knödel Sequence, $$\K_n\$$.

This is , so shortest code in bytes wins!

## Examples

1, 6   ->   [561, 1105, 1729, 2465, 2821, 6601]
2, 3   ->   [4, 6, 8]
4, 9   ->   [6, 8, 12, 16, 20, 24, 28, 40, 44]
3, 1   ->   [9]
3, 0   ->   []
21, 21 ->   [45, 57, 63, 85, 105, 117, 147, 231, 273, 357, 399, 441, 483, 585, 609, 651, 741, 777, 861, 903, 987]

• Why is 4 not in the sequence K_4? i^(4-4) = 1 mod 4 is always true. Jul 27, 2015 at 16:13
• @isaacg MathWorld has the additional condition that m > n. Jul 27, 2015 at 16:49

# Pyth, 29 28 bytes

.f&tPZ!f&q1iTZt%^T-ZQZSZvzhQ


1 byte saved thanks to Jakube and orlp.

Demonstration.

Input in the form

p
n


A fairly straightforward calculation. Relative primeness is checked via Pyth's gcd function. This code showcases .f, Pyth's "first n satisfying" function.

I have incorporated the implicit condition that m > n by starting the search for m values at n + 1.

Very straightforward implementation. Defines a binary operator n!p.

n!p=take p[m|m<-[n+1..],any((<1).mod m)[2..m-1],and[i^(m-n)modm<2|i<-[1..m],gcd i m<2]]


Example:

Prelude> 4!9
[6,8,12,16,20,24,28,40,44]

• What is m>n for? Jul 27, 2015 at 14:21
• I installed Haskell to try and figure out how to get rid of the m>n&& bit, changing m<-[4..] to m<-[n+1..] seems to work. You also get a byte count of 91!
Jul 27, 2015 at 18:21
• Neat! Thanks, @Vioz.
– lynn
Jul 27, 2015 at 19:08
• @Vioz- So you meddled with Haskell without knowing Haskell before? How did you do it? Jul 28, 2015 at 22:16
• @Vioz- first time hearing someone saying Haskell is a simple language to understand. I mostly just hear of people who think they don't understand monads or purity or how to do stuff without loops. If Haskell is easy for you, then good luck with learning more of it! (If you want to, of course) Jul 29, 2015 at 1:06

a#b=gcd a b>1