5
\$\begingroup\$

Lucky numbers are those numbers which contain only "4" and/or "5". For example 4, 5, 44, 54,55,444 are lucky numbers while 457, 987 ,154 are not.

Lucky number sequence is one in which all lucky numbers exist in increasing order for example 4,5,44,45,54,55,444,445,454,455...

Now we concatenate all the lucky numbers (in ascending order) to make a lucky string "4544455455444445454455..."

Given n, your task is to find the nth digit of the lucky string. If the digit is 4 then you have to print "F" else you have to print "E".

1<=n<=10^15
\$\endgroup\$
  • 4
    \$\begingroup\$ Interesting problem, but it is lacking a winning criteria. Please define a winning criteria before not-so-tolerant people close your question (or add a tag that define a clear winning criteria). \$\endgroup\$ – Victor Stafusa Jan 3 '14 at 20:32
  • 2
    \$\begingroup\$ Is this code-golf or popularity-contest? \$\endgroup\$ – Darren Stone Jan 3 '14 at 21:50
  • \$\begingroup\$ You should provide some test cases \$\endgroup\$ – aditsu Jan 4 '14 at 6:50
  • 3
    \$\begingroup\$ Why does this use 4 and 5 rather than 0 and 1? And why on Earth does it then switch to F and E for the output? \$\endgroup\$ – Peter Taylor Jan 4 '14 at 18:59
  • \$\begingroup\$ F our and Fiv e, I'm guessing? \$\endgroup\$ – mniip Jan 4 '14 at 19:00
10
\$\begingroup\$

JavaScript - 49

for(s=i=0;!(r=s[n+i++]);s+=i.toString(2));"FE"[r]

Execute this on a JavaScript console (tested on Node), with n set to the 1-based index of the digit you want.

Explanation:

The script builds a version of the lucky string, and stops when the character we're looking for exists.

Lucky string:        4 5 44 45 54 55
Generated string: 011011100101110111

The lucky string is equivalent to the concatenation of all binary numbers with the leading one stripped. We can get the index of the appropriate character in s from n by adding the number of leading ones in the string to skip, or, equivalently, how many binary numbers we generated. Luckily for us, we can just grab the current value of i.

It greatly helps to see the final values of s and i after running. For sake of brevity, I won't post a table here, but you can certainly check their values in the console.

Details:

s=i=0

Initializes s and i. s later becomes a string, but rather than initialize to "0", 0 works fine because of implicit type conversion.

i++

Increments i every iteration.

r=s[n+i++]

Gets the character of s at n+i (0 or 1) and stores it in r.

!(r=s[n+i++])

Loops while the character we are looking for is still undefined.

s+=i.toString(2)

Appends the next binary number in sequence to s.

"FE"[r]

Causes the expression to evaluate to F if r is 0, E if r is 1.

\$\endgroup\$
  • \$\begingroup\$ amazing! care to give an explanation of why it works? it's very couterintuitive at first sight. \$\endgroup\$ – rewritten Jan 3 '14 at 21:39
  • \$\begingroup\$ @rewritten Sure, I'll post one in a few minutes. I like to leave my code a mystery for a while. \$\endgroup\$ – Kendall Frey Jan 3 '14 at 21:41
  • \$\begingroup\$ That's really interesting. I thought about binary, but did not get to the "remove leading '1'" trick. Congratulations!!! \$\endgroup\$ – rewritten Jan 4 '14 at 22:19
  • \$\begingroup\$ @rewritten I got the idea from OEIS. (I shamelessly search sequences of numbers for problems such as this.) \$\endgroup\$ – Kendall Frey Jan 4 '14 at 22:36
3
\$\begingroup\$

GolfScript: 48

10 15?,{''+{.52=\53=|}%{&}*},{''++}*=52='F''E'if

Very inefficient. Can definitely be improved.

Explanation: 10 15?, builds a sequence of the first 10^15 numbers. The next block preceding the next comma filters the sequence down to so-called lucky numbers by converting to a string, mapping characters of the string to 1 if they equal '4' (52) or '5' (53), and then folding & over the elements. Finally, fold string concatenation across the lucky sequence to form a big string, take the nth element, and convert to 'F' or 'E' appropriately.

\$\endgroup\$
  • \$\begingroup\$ It's not the concatenation of the lucky numbers under 10^15, it's any of the first 10^15 digits of the concatenation of all the lucky numbers. Given that there are 2^n lucky numbers of n digits, it means that to get 10^15 digits you have to get lucky numbers greater than 10^40 \$\endgroup\$ – rewritten Jan 3 '14 at 21:38
  • 1
    \$\begingroup\$ But, hey, this is not about speed or feasibility... it's about the least amount of bytes! \$\endgroup\$ – rewritten Jan 3 '14 at 21:39
2
\$\begingroup\$

GolfScript, 34

Based on Kendall Frey's solution, uses 0-based indices.

~''{0):0 2base(;+.,2$)<}do='FE'1/=

Alternative solution, 44 bytes:

~0{-.0):0.2\?*.@)<}do 1$+0/2base\0%)='FE'1/=

This has the advantage that it's MUCH faster, in fact it's instant even for 15-digit inputs.

Java equivalent (more or less):

public static void f(long n) {
    long k = 0; // number of digits
    long t = 0;
    while (true) {
        k++;
        t = k << k;
        if (t > n) break;
        n -= t;
    }
    // the lucky number with 0s and 1s, prefixed with a 1
    String s = Long.toBinaryString((n + t) / k);
    int d = s.charAt((int) (n % k + 1)) - '0'; // the digit we want
    System.out.println("FE".charAt(d));
}
\$\endgroup\$
1
\$\begingroup\$

Haskell, fast

I'm aiming for the fastest program. The hidden structure of this question, as explained by Kendall Frey, is that the lucky numbers can be explained as binary numbers. But his answer is searching each number in succession, making for a terrible runtime for large numbers. Can we do better? How do we solve for n=10^15 in a speedy manner?

The length of each lucky number is the following:

x  lucky length
1  4     1
2  5     1
3  44    2
4  45    2
5  54    2
6  55    2
7  444   3
8  445   3
9  454   3
10 455   3
11 544   3
e  t     c

Note the pattern in the length increase. We first have a run of 2 same-length numbers, then 4, 8, 16, 32, ...

I'm going to use this fact to find the length of my number fast, by multiplying by two until I find the "block" of similar-length numbers, and accumulate the length up to that block. I then use divison to find out which number inside that block is the one I'm looking for, and modulo to find what digit it has.

find n =
  let (digits, n') = block n
      num = n' `div` digits
      digit = digits - (n' `rem` digits) - 1
  in case (num `div` (2^digit)) `rem` 2 of
    0 -> 'F'
    1 -> 'E'

-- Return (digits in each number in block, n-(length up to block)-1)
block n = block' n 2 0 2 1
  where
    block' n add acc pow length
      | acc+add >= n = (length, n-acc-1)
      | otherwise=
        let len' = length+1
            pow' = pow*2
            add' = len'*pow'
        in block' n add' (acc+add) pow' len'

(I stumbled across lots of off-by-one pitfalls while implementing this. Also, I didn't see aditsus speed-edit until I had already written this, but at least I bring an explanation :-) )

\$\endgroup\$
1
\$\begingroup\$

Python 2.7 based on Kendall Frey somewhat deduction of the problem xD ... well spot

s = "";n=10;i=2
while len(s) < n:
    i+=1; s+=bin(i)[3:]
print "FE"[int(s[n-1])]
\$\endgroup\$

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