0

Was looking at problem 442 in project Euler and actually I am kind of stuck with a different problem. So no spoilers here. What I am doing is the following. I am using this code to count occurrences of power of eleven in numbers (code is not optimized but it works, so forgive missing optimization)

#!/usr/bin/python

for ii in xrange (1,8):
    count1=0
    count2=0
    count3=0
    count4=0
    count5=0
    count6=0
    count7=0
    #for jj in xrange ((10**ii), (10**(ii+1))):
    for jj in xrange (1, (10**(ii+1))):
            found = False

            a="11"
            jjs=str(jj)
            if (a in jjs):
                    count1=count1+1
                    found = True
            a="121"
            if (a in jjs and not found):
                    count2=count2+1
                    found = True
            a="1331"
            if (a in jjs and not found):
                    count3=count3+1
                    found = True
            a="14641"
            if (a in jjs and not found):
                    count4=count4+1
                    found = True
            a="161051"
            if (a in jjs and not found):
                    count5=count5+1
                    found = True
            a="1771561"
            if (a in jjs and not found):
                    count6=count6+1
                    found = True
            a="19487171"
            if (a in jjs and not found):
                    count7=count7+1
                    found = True
    print "======================================================"
    print "1 <-> 10^",ii+1, " - ",10**ii, " - ", 10**(ii+1)
    print "======================================================"
    print "11       ", count1
    print "121      ", count2
    print "1331     ", count3
    print "14641    ", count4
    print "161051   ", count5
    print "1771561  ", count6
    print "19487171 ", count7
    print "Sum      ", count1+count2+count3+count4+count5
    print "------------------------------------------------------"

Now this produce an output that looks like this (I shortened it)

======================================================
1 <-> 10^ 2  -  10  -  100
======================================================
11        1
121       0
1331      0
14641     0
161051    0
1771561   0
19487171  0
Sum       1
------------------------------------------------------
======================================================
1 <-> 10^ 3  -  100  -  1000
======================================================
11        19
121       1
1331      0
14641     0
161051    0
1771561   0
19487171  0
Sum       20
------------------------------------------------------
======================================================
1 <-> 10^ 4  -  1000  -  10000
======================================================
11        280
121       18
1331      1
14641     0
161051    0
1771561   0
19487171  0
Sum       299
------------------------------------------------------
======================================================
1 <-> 10^ 5  -  10000  -  100000
======================================================
11        3691
121       260
1331      18
14641     1
161051    0
1771561   0
19487171  0
Sum       3970
------------------------------------------------------

Now I managed to find a recursive relationship between the number of occurrences of the number 11 (let's call it N_{11}(n)$) up to n. That being

N_11(n)=9*N_11(n-1)+10^(n-2)+9*N_11(n-2)

Now somehow I don't seem to be able to find the same relationship for the other powers (although I think it should be similar). Anyone willing to help? Would be greatly appreciated... Is a matter of principle :-)

Thanks in advance, Umberto

Cory Kramer
  • 114,268
  • 16
  • 167
  • 218
Umberto
  • 1,387
  • 1
  • 13
  • 29
  • Thanks for correcting the formatting @Cyber. – Umberto Apr 17 '14 at 18:21
  • You can use [this approach](http://stackoverflow.com/questions/22394257/how-to-count-find-integers-between-large-a-and-b-with-a-certain-property/22394258#22394258) combined with a finite state automaton for string matching (such as Aho-Corasick) to count the number of integers smaller than a given *U* that are eleven-free. Then you can just binary search on *U* to find the n-th such number – Niklas B. Apr 17 '14 at 18:23
  • Ok a bit too much for me for what I know about algorithms... But nonetheless interesting. I am wondering if there is an easier solution (or more elementary...). Thanks anyway for the link. – Umberto Apr 17 '14 at 18:57
  • A more mathematical approach would be to note that the non-eleven-free numbers are of the form `X + 11^n * 10^k + 10^(k + ceil(log_10(11^n)))` with `X < 10^k`. Maybe some kind of inclusion/exclusion could work too. I doubt however that there is anything special about powers of eleven, so I could just as well give you 18 numbers and ask you to find the n-th number that doesn't contain any of these as a substring. I don't think that would be any harder, but I'm not 100% sure – Niklas B. Apr 17 '14 at 19:00
  • I agree with you. Nothing special about power of eleven. As you one could simply get 18 numbers. I am pretty sure nothing would change... The only special number is 11 since it is formed by two equal digits. I am sure that this problem can be solved only with pen and paper... – Umberto Apr 17 '14 at 19:05
  • And I am a bit puzzled by your form X + 11^n * 10^k + 10^(k + ceil(log_10(11^n))) with X < 10^k... But I may be tired... – Umberto Apr 17 '14 at 19:10
  • Well actually it's X + 11^n * 10^k + Y * 10^(k + ceil(log_10(11^n))) but I don't think it yields any kind of solution – Niklas B. Apr 17 '14 at 19:35
  • Not really. I got the right formula too but it does not help really. But I am sure one can generalize the formula I found N_11(n)=9*N_11(n-1)+10^(n-2)+9*N_11(n-2) for (for example) 121 or 1331 or any set of digits. 11 is particular because is made of only 1... – Umberto Apr 17 '14 at 20:08
  • I'm not so sure. As I said, to me it looks like there is nothing special about powers of 11 in this context, and it could just be any random set of integers that are disallowed as part of the decimal representation. So I think the problem is equivalent to counting numbers that don't contain any of a given set of substrings and then my initial approach using DP with a state machine seems to be the "simplest" approach (albeit not really being simple) – Niklas B. Apr 17 '14 at 20:41
  • Actually it might be a bit simpler, because the patterns are "almost" non-overlapping (they only share leading and trailing ones) – Niklas B. Apr 17 '14 at 20:53
  • I solved it. The forum thread shows that pretty much everyone used the state machine approach with binary search on U or some simplication of it that makes use of the fact that there are only few overlaps between the patterns. So that's probably the way to go – Niklas B. Apr 17 '14 at 22:06
  • Hi thanks for taking the time. I am not familiar with the concepts. I will study them and try again. Cheers. – Umberto Apr 18 '14 at 07:49

0 Answers0