19
\$\begingroup\$

Lucky numbers (A000959) are numbers generated by applying the following sieve:

Begin with the list of natural numbers:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, ...

Now, remove every second element (\$n = 2\$, the smallest element in the list aside from 1):

1,    3,    5,    7,    9,     11,     13,     15,     17,     19,     21,     23,     25, ...

Now, remove every third element (\$n = 3\$, the next remaining element after 2):

1,    3,          7,    9,             13,     15,             19,     21,             25, ...

Now, remove every seventh element (\$n = 7\$, the next remaining element after 3):

1,    3,          7,    9,             13,     15,                     21,             25, ...

Then continue removing the \$n\$th remaining numbers, where \$n\$ is the next number in the list after the last surviving number. Next in this example is 9, then 13 and so on.

Eventually, this converges to the lucky numbers:

1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, 87, 93, 99, ...

However, we've already looked at the lucky numbers. Today, we'll be looking at a related sequence: the lucky factors (A264940). These are the values of \$n\$ that remove a specific integer \$x\$.

For example, \$x = 2\$ is removed when \$n = 2\$, so \$2\$'s lucky factor is \$2\$
Additionally, \$x = 19\$ is removed when \$n = 7\$, so \$19\$'s lucky factor is \$7\$

If \$x\$ is lucky, its lucky factor is \$0\$.

The first 50 elements of this sequence are

0, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 0, 2, 3, 2, 7, 2, 0, 2, 3, 2, 0, 2, 9, 2, 3, 2, 0, 2, 0, 2, 3, 2, 0, 2, 7, 2, 3, 2, 0, 2, 13, 2, 3, 2, 0, 2

This is a standard challenge. You may choose to:

  • Take a positive integer \$x\$ and output the lucky factor of \$x\$
  • Take a positive integer \$x\$ and output the lucky factors of each integer \$1 \le i \le x\$
  • Output the infinite list of lucky factors

This is so the shortest code in bytes wins


Test cases

 x  n
15  0
57  9
26  2
41  3
50  2
13  0
48  2
20  2
19  7
22  2
24  2
27  9
60  2
54  2
49  0
 2  2
 7  0
45 13
55 15
\$\endgroup\$
2
10
\$\begingroup\$

Python 2, 72 bytes

Takes a positive integer \$ x \$ and outputs the lucky factor of \$ x \$. Outputs via exit code.

x=input()
R=range(1,x+1)
for i in R:i+=i<2;del R[i-1::i];x>R[-1]<exit(i)

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ What... exactly is that last statement doing? Is exit(i) being compared to a boolean? \$\endgroup\$
    – hakr14
    May 4 at 1:42
  • 1
    \$\begingroup\$ @hakr14 It's using the short-circuiting effect of comparison operator chaining to save bytes from x<=R[-1]or exit(i) or x>R[-1]and exit(i). \$\endgroup\$
    – blhsing
    May 4 at 1:50
  • 1
    \$\begingroup\$ @blhsing ah, wasn't aware > short-circuited. \$\endgroup\$
    – hakr14
    May 4 at 1:53
  • 1
    \$\begingroup\$ @hakr14 it took me way too long to read it correctly, but I think it's specifically the short-circuiting effect of chained comparisons--x>R[-1]<exit(i) is equivalent to x>R[-1] and R[-1]<exit(i) (although that equivalence isn't strictly true in general, R[-1] happens not to have any side effects). \$\endgroup\$ May 4 at 2:17
7
\$\begingroup\$

R, 75 73 71 63 bytes

x=scan();a=b=1:x;while(x%in%a)a=a[-b*(T=c(a,0)[F<-F+1]+!T-1)];T

Try it online!

Returns the \$n\$-th lucky factor.

Thanks for -2 bytes to Giuseppe and -8 bytes to Dominic van Essen.

\$\endgroup\$
2
  • \$\begingroup\$ 63 bytes...? \$\endgroup\$ May 5 at 21:53
  • \$\begingroup\$ @DominicvanEssen, Awesome, this completely resolves the most inelegant part! \$\endgroup\$
    – Kirill L.
    May 6 at 8:58
5
\$\begingroup\$

Jelly, 33 27 bytes

2ịŻ‘ɼ»2$‘¤ị,ḟm¥@¥ƊƲƬṪċ¥Ðḟ⁸Ḣ

Try it online!

A full program taking an integer as its argument and printing an integer. Could almost be used as a monadic link, but the register needs to be reset to zero before each call. The TIO link has a footer that runs all of the test cases.

\$\endgroup\$
3
\$\begingroup\$

Python 2, 143 bytes

def f(x):
	m=1;n=range(1,x+1)
	while x in n and max(n)>m:m=min(q for q in n if q>m);n=[q for i,q in enumerate(n)if-~i%m]
	print 1-(x in n)and m

Try it online!

a very unintelligent and trivial implementation of this

\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 73 67 bytes

i=1
f@n_:=0Module[{k=++i},f@_/;n∣k++=n]
Print@f@Max[,2]~Do~{,∞}

Try it online!

Prints lucky factors indefinitely.

f is designed to be called on consecutive natural numbers, starting with 2,2,3,4....

Initially there is one rule defined for f: a generic definition on an argument n, intended to be called only when n is lucky. It increments a counter and adds a new, more specific definition - a sieve which applies on every nth call, for which n is the lucky factor - and returns 0 (since n is lucky).

Mathematica tries more specific definitions before more general ones. When rules have the same generality (as multiple calls on lucky numbers will generate), they're tried in order of definition. Thus a sieve is only attempted if earlier ones did not filter that number.


69 bytes

Array[Clear@f;f[i=1]=f@2;f@n_:=0Module[{k=++i},f@_/;n∣k++:=n];f,#]&

Try it online!

Function which returns the lucky factors of 1..x.

\$\endgroup\$
3
\$\begingroup\$

Python 3.8 (pre-release), 69 bytes

f=lambda n,k=2:n>=k and(f(n+n//k*~-t,k+1)if(t:=k>2<=f(k))+n%k else k)

Try it online!

Direct recursion. Returns the lucky factor of x, using False instead of 0.

\$\endgroup\$
3
\$\begingroup\$

Java (JDK), 107 bytes

x->{int s[]=new int[x+1],i=1,j,c;for(;++i<x;)for(c=j=s[i]<1?0:x;j++<x;)s[j]+=s[j]<1&&++c%i<1?i:0;return s;}

Try it online!

  • This outputs the lucky factors of each integer \$1 \le i \le x\$ in a 0-indexed array, but the mapping basically stays result[x] = factor (plus has result[0] = 0, which shouldn't be taken into consideration).

Explanation

This answer basically counts the number of zeroes, and every "lucky"-th zero is changed into the current lucky factor.

\$\endgroup\$
0
3
\$\begingroup\$

05AB1E, 37 bytes

L∞IFD®LKн©ôD€θI£®‚ˆ€¨˜}I£ILå≠÷¯vy`¸Þ‡

It's slow, ugly, and long, but it works.. :/ I might try to revisit this one from scratch later on.

Given an input \$n\$, outputs the first \$n\$ values.

Try it online.

Explanation:

L                   # Push a list in the range [1, (implicit) input]
 ∞                  # Push an infinite positive list: [1,2,3,...]
  IF                # Loop the input amount of times:
    D               #  Duplicate the infinite list
     ®L             #  Push a list in the range [1,`®`]
                    #  (`®` is -1 by default, so the first iteration is [1,0,-1])
       K            #  Remove these values from the duplicated infinite list
        н           #  Pop and only leave the first (smallest) value
                    #  (this is basically the smallest value above `®` (and 1))
         ©          #  Store it as new `®` (without popping)
          ô         #  Split the infinite list into parts of that size
           D        #  Duplicate this list of parts
            €θ      #  Only leave the last value of each part
              I£    #  Only keep the first input amount of values of this infinite list
                ®‚  #  Pair it with `®`
                  ˆ #  And pop and add it to the global array
            ۬      #  Remove the last value from each part
              ˜     #  And flatten the list
   }I£              # After the loop: only leave the first input amount of values
      IL            # Push a list in the range [1,input]
        å≠          # Check for each that it's NOT in this list
          ÷         # Integer-divide the initial [1,input] list by these 0s/1s,
                    # where division-by-0 results in 0
                    # (this basically mapped all Lucky numbers to 0s)
    ¯               # Push the global array
     vy             # Loop over each pair `y`:
       `            #  Pop and push the list and integer separated to the stack
        ¸Þ          #  Create an infinite list only containing this integer
          ‡         #  Transliterate all values in the list to the integer in our list
                    # (after which the list is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Dart, 151 143 138 bytes

f(x)=>([n,c,i,s]){for(s=[for(;i<x;)++i];n<s.last;i=s.length)for(n=s[c];i>0;c=s[i]>n?i:c)if(i--%n<1&&s.removeAt(i)==x)return n;}(0,1,0)??0;

Try it online!

Takes a positive integer x and output the lucky factor of x. I tried to reduce this as much as possible since Dart is a little verbose and that's the best I could come with.

Ungolfed:

int f(int x) {
  int c = 1;
  var s = [for(int i = 1; i <= x; i++) i];
  for (int n = 0; n < s.last;) {
    n = s[c];
    for (int i = s.length; i > 0; --i) {
      if ((i + 1) % n == 0) {
        if (s.removeAt(i) == x)
          return n;
      }
      if (s[i] > n) c = i;
    }
  }
  return 0;
}
\$\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.