# 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. – isaacg Jul 27 '15 at 16:13
• @isaacg MathWorld has the additional condition that m > n. – Martin Ender Jul 27 '15 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? – rubik Jul 27 '15 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! – Kade Jul 27 '15 at 18:21
• Neat! Thanks, @Vioz. – Lynn Jul 27 '15 at 19:08
• @Vioz- So you meddled with Haskell without knowing Haskell before? How did you do it? – proud haskeller Jul 28 '15 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) – proud haskeller Jul 29 '15 at 1:06

a#b=gcd a b>1