LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 September 3 2012

NuclearVision
Member

[Exercice]N-th fractional part of an irriational number

Like most of our exercises, this exercises was taken by Project Euler, the famous mind-refreshing, mathematical-computing exercises' website.
The exercise was posted as follows

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021...

It can be seen that the 12th digit of the fractional part is 1.

If dn represents the nth digit of the fractional part, find the value of the following expression.

d1*d10*d100*d1000*d10000*d100000*d1000000

I know this is one of the simplest exercises out there that's why i hope to see some new methodology.
My code in python takes like 4.47 seconds i am sure you guys can beat me, so come on.
I'll be hopefully the second one to post my answer otherwise, this topic will be challenge-less.
Waiting to see some codes,
Tchao.

Last edited by NuclearVision (September 3 2012)

Offline

#2 September 3 2012

Ra8
Member

Re: [Exercice]N-th fractional part of an irriational number

in PHP runs in 0.2 seconds:

<?php
$t1=microtime(true);
$s="";
$n=0;
while(strlen($s)<1e6+2){
	$s.=$n++;
}
echo $s[1e0]*$s[1e1]*$s[1e2]*$s[1e3]*$s[1e4]*$s[1e5]*$s[1e6];
echo "<br /><br />".(microtime(true)-$t1);
?>

Last edited by Ra8 (September 3 2012)

Offline

#3 September 3 2012

NuclearVision
Member

Re: [Exercice]N-th fractional part of an irriational number

@Ra8 that's astounding but I was hoping to see some of you Cpp mate.

digitlist=list("".join(map(str, xrange(1,999999))))
def d(n):
    return int(digitlist[n-1])
print d(1)*d(10)*d(100)*d(1000)*d(10000)*d(100000)*d(1000000)

Last edited by NuclearVision (September 3 2012)

Offline

#4 September 4 2012

Joe
Member

Re: [Exercice]N-th fractional part of an irriational number

Here's my code. It does not build the whole string, instead it returns the value by calculating the number being drawn. As a result the execution of d(i) is quasi-linear.

import operator
import math

def levels(n):
    return 9 * n * 10 ** (n - 1)

def face_value(i):
    def level_filler(i):
        n = 1
        yield 1
        
        while i > levels(n):
            yield int(levels(n)/n * 1.0)
            i -= levels(n)
            n += 1

        yield int(math.ceil(i / n * 1.0))

    if i == 1: return 1
    else:
        return sum(level_filler(i))

def d(i):
    h = str(face_value(i))
    l = len(h)
    k = sum(levels(x) for x in xrange(1, l)) + 1
    j = (i-k)%l
    
    return int(h[j])

# d(1) * d(10) * d(100) * d(1000) * d(10000) * d(100000) * d(1000000)
print(reduce(operator.mul, (d(10**i) for i in xrange(7))))

The code is messy, I struggled to find something to pass off as names for the functions and the variables. I'm sure it can be expressed a lot better than that.

Like most of our exercises, this exercises was taken by Project Euler, the famous mind-refreshing, mathematical-computing exercises' website.

This is absolutely wrong, the amount of PE exercises on this forum can be counted on one hand. I don't mind getting some exercises from there and work on it together, but please let's not turn this into a PE knock-off.

Offline

#5 September 4 2012

NuclearVision
Member

Re: [Exercice]N-th fractional part of an irriational number

My excuses rahmu...

Offline

#6 September 5 2012

arithma
Member

Re: [Exercice]N-th fractional part of an irriational number

This will use almost no memory. It doesn't reuse its progress though, which is a bummer, but I don't want to get sucked into this exercise no more.

import math

def d(idx):
	idx -= 1
	n = 1
	ln = len(str(n))
	while(idx>=ln):
		idx -= ln
		n += 1
		ln = len(str(n))
	s = str(n)
	return int(s[idx])

print d(1) * d(10) * d(100) * d(1000) * d(10000) * d(100000) * d(1000000)

Offline

#7 September 5 2012

Joe
Member

Re: [Exercice]N-th fractional part of an irriational number

Very cool arithma!

I follow a similar approach, but my code is messy, cryptic and looks too much like the draft paper I used to scribble my thoughts down.

Glad to see you writing Python code :)

Offline

#8 September 5 2012

arithma
Member

Re: [Exercice]N-th fractional part of an irriational number

rahmu wrote:

Very cool arithma!

I follow a similar approach, but my code is messy, cryptic and looks too much like the draft paper I used to scribble my thoughts down.

Glad to see you writing Python code :)

I really tried hard to understand your technique, but couldn't barge through it. So I decided to implement something and see if they're similar, in order to understand yours.

At any rate, being the sucker I am, I implemented something that doesn't have to recalculate what has already been calculated:

import math

def d(idx, start, n):
    idx -= start
    ln = len(str(n))
    while(idx>=ln):
        idx -= ln
        n += 1
        ln = len(str(n))
    s = str(n)
    return (int(s[idx]), idx, n)

prd = 1
idx = 1
state = (idx, 0, 1)
for i in range(7):
	print state
	prd *= state[0]
	state = d(idx*10, idx-state[1], state[2])
	idx *= 10

print prd

Offline

Board footer