CODEWITHSUNDEEP
c++parioeis
Sri Hari Vignesh
Sri Hari Vignesh

Reputation: 358

Convert PARI program to C++

I found a sequence of interest in OEIS and I want to generate the same sequence in C++ for a programming competition solution I am working on.

However I hit a roadblock understanding how the program given in the sequence page works.

Here is the program given in the page - 

(PARI) test(n)= {m=n; forprime(p=2, 5, while(m%p==0, m=m/p));                                         
return(m==1)} for(n=1, 500, if(test(n), print1(n", ")))
(PARI) a(n)=local(m); if(n<1, 0, n=a(n-1); 
            until(if(m=n, forprime(p=2, 5, while(m%p==0, m/=p)); m==1), n++); n)
(PARI) list(lim)={
lim\=1;
my(v=List(), s, t);
for(i=0, log(lim+.5)\log(5),
    t=5^i;
    for(j=0, log(lim\t+.5)\log(3),
        s=t*3^j;
        while(s <= lim,
            listput(v, s);
            s <<= 1;
        )
    )
);
vecsort(Vec(v))
};

I found out what PARI is, but I am unable to convert this program to C++. Any suggestions to help me generate the same sequence in C++ would be much appreciated.

I tried to generate the sequence in C++ with the following code snippet. But I think I am missing certain numbers in between as I fail a few tests in the online IDE.

for(int i = 0; i < 16; i++)
{
    for(int j = 0; j < 15; j++)
    {
        for(int k = 0; k < 12; k++)
        {
            std::cout<<pow(2,i)*pow(3,j)*pow(5,k)<<std::endl;
        }
    }
}

I chose 16, 15 and 12 as the limits because otherwise the result value overflows long variable type.

Upvotes: 0

Views: 481

Answers (1)

Charles
Charles

Reputation: 11479

You have three programs here, each of which serve different purposes.

The first checks if a number is 5-smooth. It simply divides by 2, 3, and 5 until it can't do so any more, and then tests if what's left is 1.

The second generates the ''n''th 5-smooth number. It uses the same idea as the first, testing each number in the range. This is very inefficient!

The third generates all 5-smooth numbers up to a given bound.

I'm going to assume that the third is what you want, because it seems most likely to be applicable to your situation. (It also helps that I am the author of that program.)

#include <iostream>
#include <vector>
#include <algorithm>

int main(void);
std::vector<long> smooth(long lim);

int main(void) {
    long lim = 1000;
    std::vector<long> v = smooth(lim);
    std::cout << "5-smooth numbers up to " << lim << ": ";
    for (std::vector<long>::iterator it = v.begin(); it != v.end(); it++) {
        std::cout << *it << ", ";
    }
    std::cout << "\n";
    return 0;
}

std::vector<long> smooth(long lim) {
    std::vector<long> v = {};
    for (long t = 1; t <= lim; t*=5) {
        for (long s = t; s <= lim; s*=3) {
            for (long n = s; n <= lim; n*=2) {
                v.push_back(n);
            }
        }
    }
    std::sort(v.begin(), v.end());
    return v;
}

This isn't a line-by-line conversion, of course; for example, I didn't use logarithms since exact logarithms aren't built-in to C++ like PARI. It's pretty fast, it finds all the 5-smooth numbers up to 1,844,674,407,370,955,161 (the highest it can do on a 64-bit machine) in a fraction of a second.

Upvotes: 1

Related Questions