cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-7 of 7 results.

A376918 Number of digit patterns of length n without common prime factors of a different digital type.

Original entry on oeis.org

1, 2, 4, 11, 51, 177, 876, 3965, 20782, 114462, 678568, 4160919, 27640938, 190402900, 1378295071, 10437144322, 82285618466, 671415306221, 5676395537455
Offset: 1

Views

Author

Dmytro Inosov, Oct 10 2024

Keywords

Comments

a(n) gives the number of distinct digit patterns (or digital types, as per A266946) such that all integers of that digital type share no common prime factor of a different digital type.
The number of remaining digit patterns not counted toward a(n) is given by A378199(n).
To check whether a digit pattern of length n with distinct digits A,B,... should be counted toward a(n), write that pattern as a linear combination of the form X1*A + X2*B + ..., where the pattern coefficients X1,X2,... consist of 0's and 1's (A007088), with 1's on positions of the corresponding digit in the pattern.
If GCD(X1,X2,...) has no prime divisors with a different digit pattern from the one we started from, the pattern is counted toward a(n). Otherwise, it is excluded.
For n of the form 10m + 3q (with m >= 1 and q >= 0), check in addition if the pattern contains all 10 distinct digits whose number of occurrences taken modulo 3 is the same for all digits from A to J. Since A + B + ... + J = 45, which is divisible by 9, such patterns are not counted toward a(n) and should be excluded.
The digital types excluded in this way result in composites for any values of the distinct digits in the pattern, without the need to run primality tests on all numbers of that digital type individually.
The requirement for a divisor of a different digital type only affects reprigits of the form AA..AA and acts to include that pattern iff the n-repunit is prime (n in A004023).
a(n) gives the upper bound for the number of distinct digital types of n-digit primes A267013(n). The two sequences are distinct, since some digit patterns such as "AAABBCABCCCAACCB" happen to contain no primes accidentally, without having a common divisor. We call such patterns primonumerophobic. Sequence A377727 = {a(n)-A267013(n)}_(n>=1) gives the number of primonumerophobic digit patterns of length n.
a(n) coincides with A267013(n) for n<10 because the shortest primonumerophobic digit patterns "AAABBBAAAB", "AABABBBBBA", and "ABAAAAABBB" have length 10.
a(n) represents row sums of T(n,k) in A378154 -- an array of contributions to a(n) with exactly k<=10 distinct decimal digits.
A164864(n) gives the total number of possible digit patterns of length n and is therefore an upper bound for a(n).

Examples

			The pattern "ABCA" is counted toward a(4) because ABCA = A*1001 + B*100 + C*10. Since GCD(1001,100,10) = 1, integers of the digital type "ABCA" (1021 in A266946) share no common prime factors.
The pattern "AA" is counted toward a(2) because AA = A*11, and 11 is a prime repunit. The only common prime factor shared by the repdigits "AA" is 11, which is of the same digital type as the original pattern.
The pattern "ABAB" is not counted toward a(4) because it is divisible by 101 for any A > 0 and B >= 0, and 101 has a different digital type from ABAB. Indeed, ABAB = A*1010+B*101, which is identically divisible by 101. In total there are four 4-digit patterns that are excluded: ABBA, AABB, AAAA (all of them divisible by 11) and ABAB (divisible by 101). Therefore, a(4) = A164864(4)-4 = 11.
The pattern "ABCDEFGHIJ" that contains all possible digits exactly once does not contribute to a(10) because its sum of digits is 1+2+...+9 = 45, which is divisible by 9. Therefore, all integers with the digital type "ABCDEFGHIJ" share the common prime factor 3.
a(23) = 37135226382208300 -- the fact that n = 23 is a term in A004023 (indices of prime repunits) simplifies the calculation of A378154(n,k) since A378761(23,k) = 0 for all k > 1. - _Dmytro Inosov_, Dec 21 2024
		

Crossrefs

Programs

  • Mathematica
    MinLength = 1; MaxLength = 12; (* the range of n to calculate a(n) for *)
    (* Function that calculates the canonical form A358497(n) *)
    A358497[k_] := FromDigits@a358497C[k]
    a358497C = Compile[{{k, _Integer}}, Module[{firstpos = ConstantArray[0, 10],
      digits = IntegerDigits[k], indx = 0}, Table[If[firstpos[[digits[[j]] + 1]] == 0, firstpos[[digits[[j]] + 1]] = Mod[++indx,10]];
      firstpos[[digits[[j]] + 1]], {j, Length[digits]}]]];
    (* Function that checks if a common prime factor of a different digital type exists *)
    DivisibilityRulesQ[pat_] := (
      If[Divisible[Length[pat], 10] && Length[Counts[pat]] == 10 &&
         AllTrue[Table[Counts[pat][[i]] == Length[pat]/10, {i, 1, 10}], TrueQ], Return[True]];
      (# != 1) && AnyTrue[Extract[# // FactorInteger, {All, 1}],
         A358497[#] != A358497[pat // FromDigits] &] &[
         Apply[GCD, Total[10^(Position[Reverse[pat], #]-1) // Flatten]& /@
         Mod[Range[CountDistinct[pat]], 10]]]
    );
    (* Function that generates all patterns that do not satisfy divisibility rules *)
    Patterns[len_, k_] := (
      Clear[dfs];
      ResultingPatterns = {};
      dfs[number_List] := If[Length[number] == len,
        If[Length[Union[If[# < 10, #, 0] & /@ number]] == k,
          AppendTo[ResultingPatterns, If[# < 10, #, 0] & /@ number]],
        Do[If[i <= 10, dfs[Append[number, i]]], {i, Range[1, Last[Union[number]] + 1]}]];
      dfs[{1}];
      FromDigits /@ Select[ResultingPatterns, ! DivisibilityRulesQ[#] &]
    );
    (* Counting the patterns T(n,k) as per A378154 and their row sums a(n) *)
    Do[Print[{n, #, Sum[#[[m]], {m, 1, Length[#]}]}] &[Table[Length[Patterns[n, j]], {j, 1, Min[10, n]}]], {n, MinLength, MaxLength}];

Formula

a(n) = Sum_{k=1..min(n,10)} T(n,k) -- row sums of A378154.
A267013(n) <= a(n) <= A164864(n).
a(n) = A164864(n) - A378199(n).
a(n) = A267013(n) + A377727(n).

Extensions

a(13)-a(19) from Dmytro Inosov, Dec 23 2024

A378154 Array read by rows: T(n,k) for k <= min(n,10) is the number of digital types of length n with exactly k distinct decimal digits without common prime factors of a different digital type.

Original entry on oeis.org

1, 1, 1, 0, 3, 1, 0, 4, 6, 1, 0, 15, 25, 10, 1, 0, 12, 84, 65, 15, 1, 0, 63, 301, 350, 140, 21, 1, 0, 80, 868, 1672, 1050, 266, 28, 1, 0, 171, 2745, 7770, 6951, 2646, 462, 36, 1, 0, 370, 8680, 33505, 42405, 22827, 5880, 750, 45, 0, 0, 1023, 28501, 145750, 246730, 179487, 63987, 11880, 1155, 55
Offset: 1

Views

Author

Dmytro Inosov, Nov 18 2024

Keywords

Comments

T(n,k) is defined as the number of distinct digit patterns (or digital types, as per A266946) of length n with k distinct digits such that all integers of that digital type share no common prime factor of a different digital type (as per A376918). Terms with k > n are omitted as trivial zeros.
To check whether a digit pattern of length n with k distinct digits A,B,... should be counted toward T(n,k), write that pattern as a linear combination of the form X1*A + X2*B + ..., where the pattern coefficients X1,X2,... consist of 0's and 1's (A007088), with 1's on positions of the corresponding digit in the pattern.
If GCD(X1,X2,...) has no prime divisors with a different digit pattern from the one we started from, the pattern is counted toward T(n,k). Otherwise, it is excluded.
For k = 10, the sum of all distinct digits A + B + ... + J = 45, which is divisible by 9. Hence, patterns in which all 10 distinct digits from A to J have the same number of occurrences in the pattern modulo 3 are identically divisible by 3 and should be excluded. This has an effect on T(n,10) whenever n takes the form 10m + 3q (with m >= 1 and q >= 0).
The digital types excluded in this way result in composites for any values of the distinct digits in the pattern, without the need to run primality tests on all numbers of that digital type individually.
The requirement for a divisor of a different digital type only affects terms with k=1, i.e. repdigits AA..AA, and acts to include that pattern iff the n-repunit is prime (n in A004023).
T(n,k) gives an upper bound for the number of contributions to A267013(n) with exactly k distinct digits.
Stirling numbers of the second kind S2(n,k) (A008277) give the total number of possible digital types of length n with k distinct digits and are therefore an upper bound for T(n,k).
T(n,1)=1 either when n=1 or when n is a term in A004023 (indices of prime repunits); otherwise T(n,1)=0 because all the repdigits A*(10^n-1)/9 are simultaneously divisibly by any proper divisor of the repunit (10^n-1)/9.
T(n,2) is nonmonotonic because a larger number of digit patterns is excluded whenever n has a large number of nontrivial divisors (A070824), resulting in anomalously low values, for example, for n=12 or n=18. This is a consequence of divisibility rules that are formulated for prime divisors of 10^r-1 or 10^r+1 (where r divides n) in terms of the sum or alternating sum of r-digit blocks, respectively [see S. Shirali, First Steps in Number Theory: A Primer on Divisibility, Universities Press, 2019, pp. 42-49].

Examples

			T(n,k) as a table (omitting terms with k > n):
---------------------------------------------------------------------------------------------
 k:  1,    2,      3,       4,       5,       6,       7,       8,      9,    10; | Total,
 n |                                                                              | A376918(n)
---------------------------------------------------------------------------------------------
 1 | 1;                                                                           |        1
 2 | 1,    1;                                                                     |        2
 3 | 0,    3,      1;                                                             |        4
 4 | 0,    4,      6,       1;                                                    |       11
 5 | 0,   15,     25,      10,       1;                                           |       51
 6 | 0,   12,     84,      65,      15,       1;                                  |      177
 7 | 0,   63,    301,     350,     140,      21,       1;                         |      876
 8 | 0,   80,    868,    1672,    1050,     266,      28,       1;                |     3965
 9 | 0,  171,   2745,    7770,    6951,    2646,     462,      36,      1;        |    20782
10 | 0,  370,   8680,   33505,   42405,   22827,    5880,     750,     45,     0; |   114462
11 | 0, 1023,  28501,  145750,  246730,  179487,   63987,   11880,   1155,    55; |   678568
12 | 0,  912,  69792,  583438, 1373478, 1322896,  627396,  159027,  22275,  1705; |  4160919
13 | 0, 3965, 261495, 2532517, 7508501, 9321312, 5715424, 1899612, 359502, 38610; | 27640938
... (for more terms, see the A-file).
The pattern "ABCA" is counted toward T(4,3) because ABCA = A*1001 + B*100 + C*10. Since GCD(1001,100,10) = 1, integers of the digital type "ABCA" (1021 in A266946) share no common prime factors.
The pattern "AA" is counted toward T(2,1) because AA = A*11, and 11 is a prime repunit. The only common prime factor shared by the repdigits "AA" is 11, which is of the same digital type as the original pattern. Since no other patterns with n=2 and k=1 exist, T(2,1)=1.
The pattern "ABAB" is not counted toward T(4,2) because it is divisible by 101 for any A > 0 and B >= 0, and 101 has a different digital type from ABAB. Indeed, ABAB = A*1010+B*101, which is identically divisible by 101. Since there are two more patterns "ABBA" and "AABB" that are excluded due to divisibility by 11, T(4,1) = S2(4,2) - 3 = 4.
The pattern "ABCDEFGHIJ" that contains all possible digits exactly once does not contribute to T(10,10) because its sum of digits is 1+2+...+9 = 45, which is divisible by 9. Therefore, all integers with the digital type "ABCDEFGHIJ" share the common prime factor 3. Since no other patterns with n=k=10 exist, T(10,10)=0.
The pattern "ABCBDEFBGHIBJ" is not counted toward T(13,10) because its sum of digits is 3*B+45, which is divisible by 3. In total there are binomial(13,4) = 715 patterns of length 13 with all 10 distinct digits in which any 4 digits are equal, and since A378761(13,10) = 0, we obtain T(13,10) = S2(13,10) - 715.
		

Crossrefs

Programs

  • Mathematica
    MinLength = 1; MaxLength = 10; (* the range of n to calculate T(n,k) for *)
    (* Function that calculates the canonical form A358497(n) *)
    A358497[k_] := FromDigits@a358497C[k]
    a358497C = Compile[{{k, _Integer}}, Module[{firstpos = ConstantArray[0, 10],
      digits = IntegerDigits[k], indx = 0}, Table[If[firstpos[[digits[[j]] + 1]] == 0, firstpos[[digits[[j]] + 1]] = Mod[++indx, 10]]; firstpos[[digits[[j]] + 1]], {j, Length[digits]}]]];
    (* Function that checks if a common prime factor of a different digital type exists *)
    DivisibilityRulesQ[pat_] := (
      If[Divisible[Length[pat], 10] && Length[Counts[pat]] == 10 &&
         AllTrue[Table[Counts[pat][[i]] == Length[pat]/10, {i, 1, 10}], TrueQ], Return[True]];
      (# != 1) && AnyTrue[Extract[# // FactorInteger, {All, 1}],
         A358497[#] != A358497[pat // FromDigits] &] &[
         Apply[GCD, Total[10^(Position[Reverse[pat], #]-1) // Flatten]& /@
         Mod[Range[CountDistinct[pat]], 10]]]);
    (* Function that generates all patterns that do not satisfy divisibility rules *)
    Patterns[len_, k_] := (
      Clear[dfs];
      ResultingPatterns = {};
      dfs[number_List] := If[Length[number] == len,
        If[Length[Union[If[# < 10, #, 0] & /@ number]] == k,
          AppendTo[ResultingPatterns, If[# < 10, #, 0] & /@ number]],
        Do[If[i <= 10, dfs[Append[number, i]]], {i, Range[1, Last[Union[number]] + 1]}]];
      dfs[{1}];
      FromDigits /@ Select[ResultingPatterns, ! DivisibilityRulesQ[#] &]);
    (* Counting the patterns T(n, k) and their sum, A376918(n) *)
    Do[Print[{n, #, Sum[#[[m]], {m, 1, Length[#]}]}] &[Table[Length[Patterns[n, j]], {j, 1, Min[10, n]}]], {n, MinLength, MaxLength}];

Formula

Sum_{k=1..min(n,10)} T(n,k) = A376918(n) (row sums).
T(n+1,n) = A000217(n) for n <= 10.
T(n,2) = 2^(n-1) - A378511(n) for n > 1.
T(n,k) <= S2(n,k) -- k'th column of A008277.
T(n,k) = S2(n,k) - A378761(n,k) for 2 <= k <= 9.
T(n,k) = S2(n,k) for n/2 < k <= 9.
T(n,k) = S2(n,k) for 2 <= k <= 9 if A378511(n) = 1 (see A378761).
T(n,10) = S2(n,10) for n = 11, 12, 14, 15, 17, 18 -- the only integers >= 10 for which no representation n = 10m + 3q with m >= 1 and q >= 0 exists and A378761(n,10)=0.
T(13,10) = S2(13,10) - binomial(13,4).
T(16,10) = S2(16,10) - binomial(16,7) - binomial(16,4)*binomial(12,4)/2.
T(19,10) = S2(19,10) - binomial(19,10) - binomial(19,7)*binomial(12,4) - binomial(19,4)*binomial(15,4)*binomial(11,4)/6.
T(23,10) = S2(23,10) - binomial(23,5)*Product_{i=1..8}(2n+1) -- since A378761(23,10)=0.

A378511 Number of partitions of the repunit A002275(n) into two mutually complementary binary vectors having a common divisor > 1 in base 10.

Original entry on oeis.org

1, 0, 1, 1, 4, 1, 20, 1, 48, 85, 142, 1, 1136, 131, 1780, 6184, 9920, 1, 75434, 1, 124468, 369142, 429508, 1, 4797008, 416966, 6114994, 22482400, 28867896, 111651, 306153842, 384525, 507438240, 1483501078, 1242075014, 743845629, 19710473036, 34300, 17721793660
Offset: 0

Views

Author

Dmytro Inosov, Nov 29 2024

Keywords

Comments

Two binary vectors of length n are mutually complementary if they are obtained from each other by inverting all the individual digits (1->0 and 0->1). The sum of any two mutually complementary binary vectors of length n is a repunit of the same length, A002275(n).
a(n) is the number of distinct unordered pairs of mutually complementary binary vectors of length n that have a common divisor > 1 as integers in base 10.
a(n) is the number of terms m in A007088 of length n that are not coprime with their 1's complement, A002275(n) - m, as integers in base 10.
Equivalently, m from A007088 is counted toward a(A055642(m)) iff GCD(m, A002275(A055642(m)) - m) > 1. Therefore a(n) is the base-10 analog of A378514.
a(n) is the sum of the first two columns, T(n,1) + T(n,2), in the triangle A378761.
For any n > 1, a(n) > 0 because the trivial partition A002275(n) = A002275(n) + 0 always counts toward a(n): GCD(A002275(n), 0) = A002275(n) > 1.
a(n) is nonmonotonic and tends to show minima for prime n, yet there are terms where n is prime yet a(n) > 1, for example a(13) = 131.
The sequence of indices n such that a(n) = 1 is a supersequence of A004023 (indices of prime repunits).

Examples

			a(1) = 0 because there is only one pair {1, 0} of mutually complementary binary vectors of length 1, and GCD(1, 0) = 1.
a(2) = 1 because out of 2 possible pairs of binary vectors of length 2, which are {10, 01} and {11, 00}, only the latter has a common divisor q > 1: q = GCD(11, 0) = 11, whereas the former is coprime, GCD(10, 1) = 1.
a(4) = 4 because out of the 8 possible pairs of mutually complementary binary vectors, exactly 4 are not coprime:
  {1000,0111}: GCD(1000, 111) = 1;
  {1001,0110}: GCD(1001, 110) = 11;
  {1010,0101}: GCD(1010, 101) = 101;
  {1011,0100}: GCD(1011, 100) = 1;
  {1100,0011}: GCD(1100, 11) = 11;
  {1101,0010}: GCD(1101, 10) = 1;
  {1110,0001}: GCD(1101, 10) = 1;
  {1111,0000}: GCD(1111, 0) = 1111.
The pair {1100010011110, 0011101100001} is counted toward a(13) because in base 10, GCD(1100010011110, 11101100001) = 53. In total, there are 131 such pairs of length 13 that share common prime factors of either 53 or 79. This exemplifies the smallest prime n such that a(n) > 1.
a(317) = 1 because 317 is a term in A004023. Indeed, if any partition of the repunit R_317 into a sum of mutually complementary binary vectors except {R_317, 0} had a nontrivial common divisor q, then the repunit itself would be divisible by q < R_317, which contradicts the fact that R_317 is prime.
		

Crossrefs

Programs

  • Mathematica
    CountNonCoprimes10[n_] := (Repunit = (10^n - 1)/9; Result = 0; Do[If[!CoprimeQ[#, Repunit-#]
      &[FromDigits[IntegerDigits[i, 2]]], Result++], {i, 2^(n-1), 2^n-1}]; Result);
    Table[CountNonCoprimes10[n], {n, 0, 25}]
    (* Alternative version of the code that uses ParallelSum *)
    SubCountNonCoprimes10[n_, k_, totk_] := (Result = 0;  Do[If[!CoprimeQ[#, Repunit-#]
      &[FromDigits[IntegerDigits[i, 2]]], Result++], {i, #[[k]], #[[k+1]]-1}]
      &[Round[Subdivide[2^(n-1), 2^n, totk]]]; Result);
    CountNonCoprimes10[n_] := (Repunit = (10^n-1)/9; ParallelSum[SubCountNonCoprimes10[n, k, $KernelCount], {k, $KernelCount}, ProgressReporting -> False]);
    Table[CountNonCoprimes10[n], {n, 0, 25}]

Formula

a(n) <= A000325(n-1) = 2^(n-1) - n + 1;
a(A004023(n)) = 1.

A385539 Total number of distinct partitions of the repunit A002275(n) into an arbitrary number of complementary binary vectors having a common divisor > 1 in base 10.

Original entry on oeis.org

1, 0, 1, 1, 4, 1, 26, 1, 175, 365, 1512, 1, 52611, 274, 426897, 3072870, 10670148, 1, 879525398, 1
Offset: 0

Views

Author

Dmytro Inosov, Jul 02 2025

Keywords

Comments

Complementary binary vectors are as per A378761.
a(n) gives the total number of distinct unordered tuples of complementary binary vectors of length n (including those with leading zeros) that have a common divisor > 1 as integers in base 10. Since any such tuple sums up to the repunit A002275(n), it corresponds to an integer partition of the repunit.
For n <= 5, a(n) coincides with A378511(n).
Starting from n=2, a(n) gives the row sums of T(n,k) in A378761.
a(n) = 1 for all n in A004023 (indices of prime repunits).
a(n) = 1 iff n is a term in A385537.

Examples

			a(4) = A378511(4) = A378761(4,1) + A378761(4,2) = 4.
The only partition that counts toward A378761(4,1) is the trivial partition {1111} with only one part.
Among the possible pairs of nonzero binary vectors of length 4, exactly 3 are not coprime and therefore count toward A378761(4,2):
  {1000,0111}: GCD(1000, 111) = 1;
  {1001,0110}: GCD(1001, 110) = 11;
  {1010,0101}: GCD(1010, 101) = 101;
  {1011,0100}: GCD(1011, 100) = 1;
  {1100,0011}: GCD(1100, 11) = 11;
  {1101,0010}: GCD(1101, 10) = 1;
  {1110,0001}: GCD(1110, 1) = 1.
Longer tuples cannot count toward a(4) because for any of them at least one of its binary vectors must contain just a single "1" (with all other digits zero). It is, therefore, a power of 10 (A011557) and cannot have nontrivial common divisors with the repunit A002275(n).
		

Crossrefs

Cf. A385537. Row sums of A378761.

Programs

  • Python
    from math import gcd
    from sympy.utilities.iterables import multiset_partitions
    def A385539(n):
        return sum(1 for p in multiset_partitions([10**k for k in range(n)]) if gcd(*(sum(t) for t in p))!=1) # Pontus von Brömssen, Jul 16 2025

Formula

a(A385537(m)) = 1.
a(n) <= A277364(n).

A378199 Number of digit patterns of length n such that all integers of that digital type share a common prime factor of a different digital type.

Original entry on oeis.org

0, 0, 1, 4, 1, 26, 1, 175, 365, 1513, 1, 52611, 989, 426897, 3072870, 11132038, 1, 879525398, 316025138
Offset: 1

Views

Author

Dmytro Inosov, Nov 19 2024

Keywords

Comments

a(n) gives the number of distinct digit patterns (or digital types, as per A266946) such that all integers of that digital type share a common prime factor of a different digital type.
The number of remaining digit patterns not counted toward a(n) is given by A376918(n).
A particular digit pattern of length n is counted toward a(n) if it is not counted toward A376918(n).
All digital types counted toward a(n) result in composites for any values of the distinct digits in the pattern, without the need to run primality tests on all numbers of that digital type individually.
The requirement for a divisor of a different digital type only affects reprigits of the form AA..AA and acts to exclude that pattern iff the n-repunit is prime (n in A004023).
A164864(n) gives the total number of possible digit patterns of length n and is therefore an upper bound for a(n).
a(n) is nonmonotonic and takes on small values for prime n and large values for n with a large number of nontrivial divisors (A070824). This is a consequence of divisibility rules that are formulated for prime divisors of 10^r-1 or 10^r+1 (where r divides n) in terms of the sum or alternating sum of r-digit blocks, respectively [see S. Shirali, First Steps in Number Theory: A Primer on Divisibility, Universities Press, 2019, pp. 42-49].
a(n) coincides with row sums of T(n,k) in A378761 for n = 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 15, 17, 18. - Dmytro Inosov, Dec 23 2024

Examples

			For n=2, there are only two possible digit patterns, "AA" and "AB". Neither of them is counted toward a(2) because the common prime factor of all integers with the pattern "AA" is 11, which is a prime repunit and is therefore of the same digital type "AA", whereas integers of the digital type "AB" have no common prime factors. Indeed, AB = 10*A + 1*B, and GCD(10,1)=1.
For n=3, the repdigit pattern "AAA" is counted toward a(3) because the repunit 111 is not a prime, hence all integers of the digital type "AAA" are divisible by prime factors of 111, which are 3 and 37, both of a different digital type from "AAA".
Counterexample: The digit pattern "ABA" is not counted toward a(3) because ABA = 101*A + 10*B, and since GCD(101,10) = 1, this digital type has no common prime factors.
The pattern "ABAB" is counted toward a(4) because it is divisible by 101 for any A > 0 and B >= 0, and 101 has a different digital type from ABAB. Indeed, ABAB = A*1010 + B*101, which is identically divisible by 101. In total there are four 4-digit patterns that are counted: ABBA, AABB, AAAA (all of them divisible by 11) and ABAB (divisible by 101). Therefore, a(4) = 4.
The pattern "ABCDEFGHIJ" that contains all possible digits exactly once is counted toward a(10) because its sum of digits is 1+2+...+9 = 45, which is divisible by 9. Therefore, all integers with the digital type "ABCDEFGHIJ" share the common prime factor 3.
		

Crossrefs

Programs

  • Mathematica
    MinLength = 1; MaxLength = 12; (* the range of n to calculate a(n) for *)
    (* Function that calculates the canonical form A358497(n) *)
    A358497[k_] := FromDigits@a358497C[k]
    a358497C = Compile[{{k, _Integer}}, Module[{firstpos = ConstantArray[0, 10],
      digits = IntegerDigits[k], indx = 0}, Table[If[firstpos[[digits[[j]] + 1]] == 0, firstpos[[digits[[j]] + 1]] = Mod[++indx,10]]; firstpos[[digits[[j]] + 1]], {j, Length[digits]}]]];
    (* Function that checks if a common prime factor of a different digital type exists *)
    DivisibilityRulesQ[pat_] := (
      If[Divisible[Length[pat], 10] && Length[Counts[pat]] == 10 &&
         AllTrue[Table[Counts[pat][[i]] == Length[pat]/10, {i, 1, 10}], TrueQ], Return[True]];
      (# != 1) && AnyTrue[Extract[# // FactorInteger, {All, 1}],
         A358497[#] != A358497[pat // FromDigits] &] &[
         Apply[GCD, Total[10^(Position[Reverse[pat], #]-1) // Flatten]& /@
         Mod[Range[CountDistinct[pat]], 10]]]);
    (* Function that generates all patterns that satisfy divisibility rules *)
    Patterns[len_, k_] := (
      Clear[dfs];
      ResultingPatterns = {};
      dfs[number_List] := If[Length[number] == len,
        If[Length[Union[If[# < 10, #, 0] & /@ number]] == k,
          AppendTo[ResultingPatterns, If[# < 10, #, 0] & /@ number]],
        Do[If[i <= 10, dfs[Append[number, i]]], {i, Range[1, Last[Union[number]] + 1]}]];
      dfs[{1}];
      FromDigits /@ Select[ResultingPatterns, DivisibilityRulesQ[#] &]);
    (* Counting the patterns with k distinct digits and their row sums a(n) *)
    Do[Print[{n, #, Sum[#[[m]], {m, 1, Length[#]}]}] &[Table[Length[Patterns[n, j]], {j, 1, Min[10, n]}]], {n, MinLength, MaxLength}];

Formula

a(n) = A164864(n) - A376918(n).
a(n) = A164864(n) - A267013(n) - A377727(n).
a(n) <= A164864(n).

Extensions

a(15)-a(19) from Dmytro Inosov, Dec 23 2024

A385537 Indices k such that the repunit (10^k-1)/9 is coprime with any other nonzero binary vector of the same length in base 10.

Original entry on oeis.org

0, 1, 2, 3, 5, 7, 11, 17, 19, 23
Offset: 1

Views

Author

Dmytro Inosov, Jul 02 2025

Keywords

Comments

k is a term iff A378511(k) <= 1.
k is a term iff A385539(k) <= 1.
a(n) contains all indices of prime repunits A004023 as a subsequence.
If A378199(k) <= 1, then k is a term in this sequence, however the inverse is not true. The smallest counterexample is k = 19.
a(11) >= 59. - Michael S. Branicky, Jul 03 2025

Examples

			0 is a term because A002275(0) = 0, which is coprime with the only other binary vector of the same length, which is 1.
1 is a term because A002275(1) = 1, there are no other nonzero binary vectors of length 1, and any statement about the elements of an empty set is true.
2 is a term because 11 is a repunit prime.
3 is a term because 111=3*37 is coprime with all other nonzero binary vectors of length 3, which are 001, 010, 011, 100, 101, 110. None of them is divisible by 3 or 37.
Counterexample: 4 is not a term because the repunit 1111 is not coprime with 1100. They are both divisible by 11.
		

Crossrefs

Supersequence of A004023.

Programs

  • PARI
    isok(k) = my(x=(10^k-1)/9); for (i=1, 2^k-2, if (gcd(fromdigits(binary(i)), x) != 1, return(0)); ); return(1); \\ Michel Marcus, Jul 03 2025

Formula

A385579(a(n)) = 1.

A385579 Smallest prime factor that the repunit(n) = (10^n-1)/9 shares with at least one other binary vector of the same length in base 10, or 1 if they are coprime.

Original entry on oeis.org

1, 1, 1, 1, 11, 1, 3, 1, 11, 3, 11, 1, 3, 53, 11, 3, 11, 1, 3, 1, 11, 3, 11, 1, 3, 41, 11, 3, 11, 3191, 3, 2791, 11, 3, 11, 41, 3, 2028119, 11, 3, 11, 83, 3, 173, 11, 3, 11, 35121409, 3, 239, 11, 3, 11, 107, 3, 41, 11, 3, 11
Offset: 0

Views

Author

Dmytro Inosov, Jul 03 2025

Keywords

Comments

a(n) is the smallest prime factor that divides both the decimal repunit (10^n-1)/9 and at least one other smaller decimal number consisting of only 0's and 1's.
a(n)=1 iff n is a term in A385537 (indices of repunits coprime with all other binary vectors of the same length).

Examples

			a(3) = 1 because 111 = 3*37 is coprime with all other nonzero binary vectors of length 3, which are 001, 010, 011, 100, 101, 110. None of them is divisible by 3 or 37.
a(4) = 11 because 11 is the smallest prime factor of 1111 which it shares, for example, with the binary vector 0011.
		

Crossrefs

Programs

  • Mathematica
    F[d_] := Min[Select[Table[Min[Transpose[FactorInteger[GCD[FromDigits[IntegerDigits[i,2]],(10^d-1)/9]]][[1]]], {i, 1, 2^d-2}], # > 1 &]];
    Table[If[# < \[Infinity], #, 1] &[F[n]], {n, 0, 25}]
  • PARI
    a(n) = my(x=(10^n-1)/9, m=oo, b=0, z); for (i=1, 2^n-2, my(y=fromdigits(binary(i))); if ((z=gcd(y, x)) != 1, b=1; m = min(m, vecmin(factor(z)[,1])); ); ); if (b, m, 1); \\ Michel Marcus, Jul 03 2025

Formula

If a(n) > 1, A067063(n) <= a(n) <= A003020(n).
Showing 1-7 of 7 results.