using System.Collections.Generic; using System.Linq; using System.Text.RegularExpressions; namespace OEIS_Prime_Factors { public static class A3242xx { public static bool IsA324260(long n, long[] distinctFactors) { // subsequence of A324257 without multiplicity of each distinct factor if (!IsA324257(n, distinctFactors)) return false; string nStr = n.ToString(); bool[] pUsed = new bool[distinctFactors.Length]; int pCount = 0; bool[] digitUsed = new bool[nStr.Length]; // // first pass handle factors with no choice of location to steer the factors with // multiple options into the best slot for (int i = 0; i < distinctFactors.Length; i++) { if (pUsed[i]) continue; long p = distinctFactors[i]; int nCount = Regex.Matches(nStr, p.ToString()).Count; if (nCount == 1) { int index = nStr.IndexOf(p.ToString()); for (int offset = 0; offset < p.ToString().Length; offset++) { digitUsed[index + offset] = true; } pUsed[i] = true; pCount++; } } // check if we're done bool stat = true; foreach (bool b in digitUsed) { if (!b) { stat = false; break; } } if (stat == true) return true; // // second pass add remaining factors in reverse order of size to minimize collisions // // note this could theoretically give false negatives if the factors are overlapping just so. // Manual checking of all A324257 terms indicates that this doesn't happen for n < 2.5x10^10. // Importantly this will never give a false positive so no erroneous terms can appear in the sequence. for (int i = distinctFactors.Length - 1; i >= 0; i--) { if (pUsed[i]) continue; long p = distinctFactors[i]; int index = -1; bool stop = false; while (!stop && (index = nStr.IndexOf(p.ToString(), index + 1)) != -1) { for (int offsetUnused = 0; offsetUnused < p.ToString().Length; offsetUnused++) { if (!digitUsed[index + offsetUnused]) { // unused digit at this location place it here for (int offsetPlace = 0; offsetPlace < p.ToString().Length; offsetPlace++) { digitUsed[index + offsetPlace] = true; } pUsed[i] = true; pCount++; stop = true; break; } } } } stat = true; foreach (bool b in digitUsed) { if (!b) { stat = false; break; } } return stat; } public static bool IsA324257(long n, long[] distinctFactors) { bool stat = true; string nStr = n.ToString(); bool[] digitUsed = new bool[nStr.Length]; foreach (long p in distinctFactors) { if (!nStr.Contains(p.ToString())) { // n doesn't contain this factor stat = false; break; } else { // all digits in n need to be used int index = -1; while ((index = nStr.IndexOf(p.ToString(), index + 1)) > -1) { for (int offset = 0; offset < p.ToString().Length; offset++) { digitUsed[index + offset] = true; } } } } foreach (bool b in digitUsed) { if (!b) { stat = false; break; } } return stat; } } }