Created
February 22, 2019 15:57
-
-
Save Vaguery/fb098a399218bdae02cb1e4c0b359d23 to your computer and use it in GitHub Desktop.
To practice coding, I want to write a function which, given a strictly positive integer `p`, produces the _smallest_ `q` such that `p*q` is pandigital
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| require 'pp' | |
| require 'prime' | |
| # for integer p in the given range, find the smallest integer q such that p*q is a pandigital number (has at least one of every digit) | |
| p_range = (1..10) | |
| @digits = (0..9).to_a.collect {|d| d.to_s} | |
| def pandigital?(number) | |
| number.to_s.chars.uniq.sort == @digits | |
| end | |
| def prime_factors(number) | |
| decomposition = number.prime_division | |
| pfactors = [] | |
| decomposition.each do |pf| | |
| pfactors = pfactors + [pf[0]]*pf[1] | |
| end | |
| return pfactors | |
| end | |
| def every_binary(length) | |
| [true,false].repeated_permutation(length) | |
| end | |
| def split_array(array,mask) | |
| good = [] | |
| bad = [] | |
| (0...array.length).each do |idx| | |
| mask[idx] ? (good << array[idx]) : (bad << array[idx]) | |
| end | |
| return [good,bad] | |
| end | |
| def product(numbers) | |
| numbers.inject(1,:*) | |
| end | |
| def all_pairs(number) | |
| pf = prime_factors(number) | |
| every_binary(pf.length).collect do |mask| | |
| factors = split_array(pf,mask) | |
| factors.collect {|f| product(f)}.sort | |
| end.uniq.sort | |
| end | |
| @discoveries = {} | |
| ["0","2","3","4","5","6","7","8","9"].permutation(9).each_with_index do |p,i| | |
| n = (["1"]+p).join("").to_i | |
| p "#{n}: #{@discoveries.count}" if (i % 10000 == 0) | |
| pairs = all_pairs(n) | |
| pairs.each do |pair| | |
| idx = pair[0] | |
| @discoveries[idx] = pair[1] if @discoveries[idx].nil? | |
| end | |
| end | |
| pp @discoveries.sort |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The output of the thing above looks like this (abbreviated to fit here):