79 FREE

Computer Science Level pending

An integer is called N-free if its decimal expansion does not contain any substring representing a power of N except 1.

Let E(n) be the nth positive 79-free integer. For example E(1234) = 1256 and E(98765) = 102813.

Find the largest 3 digits of E( 10^{7} ) and type them in ascending order.

P.S. This is a Computer Science Problem and has almost been taken from P $$@


The answer is 668.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Priyanka Banerjee
Dec 31, 2013

JAVA CODE ::

import java.io.*;

import java.math.*;

class P442

{

public static void main(String args[])

{

    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    long i=0L,c=0L,d=0L;

    P442 obj=new P442();

    for(i=1L;;i++)

    {

        if(obj.fun(i,1)==1)

        {

            d=i;

            c++;

        }

        if((i<0)||(d<0)||(c<0))

            break;

        if(c==10000000L)

            break;

    }

    System.out.println(i+"          "+d);

}

long fun(long x,long n)

{

    int v=0,w=0;

    long p=0,q=0,a=0,t=0,b=0;

    q=(long)Math.pow(79,n);

    if(q>x)

        return 1;

    String s=""+x,k=""+q,d="";

    a=(long)s.length();

    t=(long)k.length();

    for(p=0;p<=a-t;p++)

    {

        v=(int)p;

        w=(int)(p+t);

        d=s.substring(v,w);

        b=Long.parseLong(d);

        if(b==q)

            return 0;

    }

    return fun(x,n+1);

}

}

OUTPUT::

--------------------Configuration: <Default>--------------------

10618506 10618506

Process completed.

Thus the answer is 668 ...

I was very much mesmerised by the problem in Project Euler and I used this same code with modifications to solve the problem given in the problem link but my program ran for 25 mins and then there was the alarm when the CPU temperature crossed 45 degree celsius , so I couldnt answer that problem ...

It will be nice and helpful if all people post the time taken by their code to compute the answer ... mine took around 55.28 seconds

Priyanka Banerjee - 7 years, 5 months ago

Log in to reply

Similar approach ........ took more than a minute ...

Santanu Banerjee - 7 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...