Write a program or script to find Lucky Numbers

Heiko Dudzus — Mon, 12 Feb 2018 18:01:43 +0000

Lucky numbers

After the "Happy Numbers" challenge, here are "Lucky Numbers": Some positive integer numbers are lucky, because they pass the sieve of Josephus.

The 1 is lucky by definition.

The successor of 1 is 2. So, every second number gets eliminated:
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, ...

The next number is 3. Now, every third number gets eliminated:
1, 3, 7, 9, 13, 15, 19, 21, ...

Number 3 is lucky! It's successor is 7. Now, every seventh number gets eliminated. And so on.

Read more about it in this Wikipedia article.

Challenge

1) Write a program or script in your language of choice, that prints the lucky numbers between 1 and n.
2) Try to make it as fast as possible for sieving lucky numbers between 1 and a million. (Perhaps it is sensible to measure the time without printing the results.)

Edit: Consider to start with odd numbers.

I found it especially interesting to make it fast. That seems to primarily depend on the used data structure. It has to meet different requirements that sometimes seemed contradictive. I am really curious, what data structures you use in your implementation.

Verification

There are

23 lucky numbers below 100,
153 are below 1000,
1118 are below 10000,
8772 are below 100000,
and among the first million positive integers 71918 are lucky.

The lucky numbers between 1 and 300:

[1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, 87, 93, 99, 105, 111, 115, 127, 129, 133, 135, 141, 151, 159, 163, 169, 171, 189, 193, 195, 201, 205, 211, 219, 223, 231, 235, 237, 241, 259, 261, 267, 273, 283, 285, 289, 297]

Challenge - Print Spiral

Heiko Dudzus — Sat, 18 Nov 2017 18:07:56 +0000

Level 1

Write a program in the language of your choice that will display a ”spiral” of n × n numbers.
For example, here’s what the spiral looks like for n = 10:

*Main> printSpiral 10
99 98 97 96 95 94 93 92 91 90
64 63 62 61 60 59 58 57 56 89
65 36 35 34 33 32 31 30 55 88
66 37 16 15 14 13 12 29 54 87
67 38 17  4  3  2 11 28 53 86
68 39 18  5  0  1 10 27 52 85
69 40 19  6  7  8  9 26 51 84
70 41 20 21 22 23 24 25 50 83
71 42 43 44 45 46 47 48 49 82
72 73 74 75 76 77 78 79 80 81
*Main>

Level 2

Make sure your program uses constant (or linear) space. This means, it is not allowed to build an array before printing it (or to build another data structure consuming space with O( n^2 ).

Idea found here: https://www.quora.com/What-are-some-interesting-puzzles-asked-in-computer-science-programming-technical-interviews

Post your solution in the comments below.

Clarification

For a solution in O(n) it is allowed to build a String (or Array,...) for a single line, but still not to build an array containing all information contained in the spiral. Perhaps this fits better to your language of choice or it is good for building a prototype,... Thanks for asking, Evan Oman.

DEV Community: Heiko Dudzus