10
\$\begingroup\$

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

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]
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Why is 4 not in the sequence K_4? i^(4-4) = 1 mod 4 is always true. \$\endgroup\$
    – isaacg
    Jul 27 '15 at 16:13
  • 1
    \$\begingroup\$ @isaacg MathWorld has the additional condition that m > n. \$\endgroup\$ Jul 27 '15 at 16:49
7
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

Haskell, 89 bytes

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)`mod`m<2|i<-[1..m],gcd i m<2]]

Example:

Prelude> 4!9
[6,8,12,16,20,24,28,40,44]
\$\endgroup\$
9
  • 2
    \$\begingroup\$ What is m>n for? \$\endgroup\$
    – rubik
    Jul 27 '15 at 14:21
  • 1
    \$\begingroup\$ 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! \$\endgroup\$
    – Kade
    Jul 27 '15 at 18:21
  • 1
    \$\begingroup\$ Neat! Thanks, @Vioz. \$\endgroup\$
    – Lynn
    Jul 27 '15 at 19:08
  • 1
    \$\begingroup\$ @Vioz- So you meddled with Haskell without knowing Haskell before? How did you do it? \$\endgroup\$ Jul 28 '15 at 22:16
  • 1
    \$\begingroup\$ @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) \$\endgroup\$ Jul 29 '15 at 1:06
2
\$\begingroup\$

Haskell, 90

a#b=gcd a b>1
n!p=take p[m|m<-[n+1..],any(m#)[2..m-1],all(\i->m#i||mod(i^(m-n))m<2)[1..m]]

much the same as @Marius 's answer, though developed independently.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.