Project Euler #52: Permuted multiples

Sort by

recency

|

23 Discussions

|

  • + 0 comments

    100% python3

    # Enter your code here. Read input from STDIN. Print output to STDOUT
    
    N, k = map(int, input().split())
    
    primes = {0: 2, 1: 3, 2: 5, 3: 7, 4: 11, 5: 13, 6: 17, 7: 19, 8: 23, 9:29}
    
    def rootval(n):
        s = 1
        while n > 0:
            s *= primes[n%10]
            n = n // 10
        return(s)
        
    n = 125874
    while n <= N:
        tmp, val = [n], rootval(n)
        for i in range(2, k+1):
            if val == rootval(n*i):
                tmp.append(n*i)
            else:
                break
        else:
            print(*tmp)
        n += 1
    
  • + 0 comments

    Simple solution in Python 3:

    n,k=map(int,input().strip().split())
    for i in range(10,n+1):
        if all(sorted(list(str(i)))==sorted(list(str(i*j))) for j in range(2,k+1)):
            print(*[i*x for x in range(1,k+1)])
    
  • + 0 comments

    JAva Code

    import java.io.*;
    import java.util.*;
    
    public class Solution {
    
        static int[] digits = new int[10];
    
        static boolean hasSameDigits(int num1, int num2) {
            for (int i = 0; i < 10; i++) {
                digits[i] = 0;
            }
            while (num1 != 0) {
                digits[num1 % 10]++;
                num1 /= 10;
            }
            while (num2 != 0) {
                digits[num2 % 10]--;
                num2 /= 10;
            }
            for (int i = 0; i < 10; i++) {
                if (digits[i] != 0) {
                    return false;
                }
            }
            return true;
        }
    
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            for (int i = 1; i <= n; i++) {
                int flag = 0;
                for (int j = 2; j <= k; j++) {
                    if (!hasSameDigits(i, j * i)) {
                        break;
                    } else {
                        flag++;
                    }
                }
                if (flag == k - 1) {
                    for (int z = 1; z <= k; z++) {
                        System.out.print(i * z + " ");
                    }
                    System.out.println();
                }
            }
        }
    }
    
  • + 0 comments

    100 points/- python3

    item=input().split()
    n,k=int(item[0]),int(item[1])
    
    def ispermuted(n,n_):
        n=str(n)
        n_=str(n_)
        if sorted(n)==sorted(n_):
            return True
        else:
            return False
    
    for i in range(1,n+1):
        if all([ispermuted(i,i*j) for j in range(2,k+1)]):
            print(*[i*j for j in range(1,k+1)])
        
    
  • + 0 comments

    For this and also problem 33 I found it very useful to implement a function which returns an integer that is invariant to permuting the digits in .

    This can be done by returning a product of prime factors where the exponents are the number of times each digit occur in n.

    In python this can be implemented as follows:

    pfs = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
    
    def p(n, ten_pfs=pfs):
        result = 1
        while n:
            n, d = divmod(n, 10)
            result *= pfs[d]
        return result
    

    So for the example given . Then it is just a matter of finding those where by iterating over the possible values of .