Euler Projesi 204. Soru

5 ten büyük asal çarpanı olmayan bir pozitif sayıya bir Hamming sayısı denir. Hamming sayıları 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... şeklinde verilebilir. 10⁸ den küçük 1105 tane Hamming sayısı vardır.

n den büyük asal çarpanı olmayan bir pozitif sayıya bir n-tipinde genelleştirilmiş Hamming sayısı denir. Dolayısıyla Hamming sayıları aslında 5-tipinde genelleştirilmiş Hamming sayılarıdır.

Şimdi, 10⁹ dan küçük 100-tipinde kaç tane genelleştirilmiş Hamming sayısı vardır?

Cevap: 2944730
C/C++:

#include <stdio.h>


int main()  {

    int pr[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
    int A[100],i,j,p,sp,k;
    int s=0;
    for(i=1;i<1000000000;i+=100)  {
        for(j=0;j<100;j++)  A[j]=i+j;
        for(j=0;j<25;j++)  {
            p=pr[j];
            sp=p-(i%p);
            if(sp==p)  sp=0;
            for(k=sp;k<100;k+=p)  {
                A[k]/=p;
                while(A[k]%p==0)  A[k]/=p;
            }
        }
        for(j=0;j<100;j++)
            if(A[j]==1)  s++;
    }
    printf("%d\n",s);
    return 0;
}

Maple:

ham:=proc(nb,factmin,maxi,type)
> local i,somme;
> somme:=1;
> i:=factmin;
> while i<=type do
>   if nb*i<=maxi then somme:=somme+ham(nb*i,max(factmin,i),maxi,type) fi;
>   i:=nextprime(i);
> od;
> somme
> end:  

ham(1,2,10^9,100);

Pascal:

program bidon;

uses minimaple;

function max(a,b:int64):int64;
begin
  if a-b>0 then max:=a else max:=b;
end;

function ham(nb,factmin,maxi,typee:int64):int64;
var i,somme:int64;
begin
  somme:=1;
  i:=factmin;
  while i<=typee do
  begin
    if nb*i<=maxi then somme:=somme+ham(nb*i,max(factmin,i),maxi,typee);
    i:=nextprime(i);
  end;
  ham:=somme;
end;

begin
 writeln(ham(1,2,1000000000,100));
end.

Java:

public class Puzzle204 {

	static int[] primes = {2,3,5,7,11,13,17,19,23,29,
		31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		System.out.println(hamming(1000000000, primes.length-1));		
		System.out.println(System.currentTimeMillis()-start);
	}

	private static int hamming(int i, int j) {
		if(j==0) return (int) (Math.log(i)/Math.log(2)) + 1;		
		else {
			int result=0;
			while (i>0) {
				result += hamming(i, j-1);
				i/=primes[j];			
			}
			return result;
		}
	}

}

Matlab:

function ret = Hamming_Numbers(bound, min_factor, max_factor)

    factors = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97];
    factors = factors(factors >= min_factor & factors <= min(max_factor, bound));
    
    ret = 1;
    if bound >= min_factor
        for i = 1:length(factors)
            ret = ret + Hamming_Numbers(floor(bound/factors(i)), factors(i), max_factor);
        end
    end

Mathematica:

PrimeList := Array[Prime, 25]
Test[max_, current_, next_] := 
 If[next == 0, If[current > max, Return[0], Return[1]],
  Module[{sum = 0, x = current, factor = PrimeList[[next]]}, 
   While[x < max, sum += Test[max, x, next - 1]; x *= factor]; 
   sum]]
ProjectEuler0204[] := Test[10^9, 1, 25] + 1
Timing[ProjectEuler0204[]]