0
$\begingroup$

I am trying to write a function that is supposed to return a list of all complementary k-tuples of integers consisting of only 0's and 1's such that every tuple is not coprime setwise (i.e. GCD of all k integers is > 1). The integers are considered integers in base 10, despite having only 2 digits.

My original version of the code that returns the correct result looks like this:

Clear[NonCoprimeList];
NonCoprimeList[n_, m_] := NonCoprimeList[n, m] = 
  If[n == 0, {{}}, If[m == 1, {{FromDigits[IntegerDigits[2^n - 1, 2]]}},
    FullList = Flatten[Table[Table[
          Prepend[FromDigits /@
            IntegerDigits[2^(Flatten[Position[Reverse[IntegerDigits[i, 2]], 0]] - 1).# &
/@ (Reverse[IntegerDigits[#, 10, Count[IntegerDigits[i, 2], 0]]] & /@ #[[j]]), 2], 
           FromDigits[IntegerDigits[i, 2]]], {j, Length[#]}] &[
        NonCoprimeList[Count[IntegerDigits[i, 2], 0], m - 1]], {i, 2^(n - 1), 2^n - 2}], 1]]]
T[n_, k_] := Length[#] &[Select[GCD @@ # > 1 &][NonCoprimeList[n, k]]];
T[8, 3]

The output of this code is T[8, 3] = 98.

Instead of applying Select[GCD @@ # > 1 &][...] at the end to the whole array, I want to place it inside the function definition and use the fact that k integers cannot have GCD > 1 if k - 1 are already setwise coprime. So I am changing the code as follows:

Clear[NonCoprimeList];
NonCoprimeList[n_, m_] := NonCoprimeList[n, m] = 
  If[n == 0, {{}}, If[m == 1, {{FromDigits[IntegerDigits[2^n - 1, 2]]}},
    FullList = Select[GCD @@ # > 1 &][Flatten[Table[Table[          
           Prepend[FromDigits /@
             IntegerDigits[2^(Flatten[Position[Reverse[IntegerDigits[i, 2]], 0]] - 1).# &
/@ (Reverse[IntegerDigits[#, 10, Count[IntegerDigits[i, 2], 0]]] & /@ #[[j]]), 2], 
            FromDigits[IntegerDigits[i, 2]]], {j, Length[#]}] &[
         NonCoprimeList[Count[IntegerDigits[i, 2], 0], m - 1]], {i, 2^(n - 1), 2^n - 2}], 1]]]]
T[n_, k_] := Length[NonCoprimeList[n, k]];
T[8, 3]

Suddenly, it now returns a different result, T[8, 3] = 84.

I spent the whole day trying to figure out why these two codes are not equivalent. I found the triples that the second code "misses" for some reason, e.g. {10100000, 1011010, 101}. This must be included because GCD[10100000, 1011010, 101] == 101.

Can anyone please help me understand what is going on?

Or maybe you can suggest a better way to define this function?

Improve this question
$\endgroup$
14
  • $\begingroup$ I need more explanation of what you're trying to do. Using your first definition, which you say gives correct results,, NonCoprimeList[4, 2] gives me {{1001, 110}, {1010, 101}, {1100, 11}}. Why should that not include {1111,11}? $\endgroup$ Commented Nov 22, 2024 at 19:38
  • $\begingroup$ And just to make sure I understand, am I correct in assuming that the argument n is meant as a sort of maximum to the search (i.e. you'll only search up to 1111 when n is 4, for example)? And the parameter m is the size of the non-coprime sets you're looking for, correct? $\endgroup$ Commented Nov 22, 2024 at 19:40
  • $\begingroup$ Oh wait, are you looking for sets where the number of appearances of the digit 1 across the whole set is constrained by the argument n? $\endgroup$ Commented Nov 22, 2024 at 19:56
  • $\begingroup$ The integers are complementary, meaning they must add up to a repunit. $\endgroup$ Commented Nov 22, 2024 at 20:18
  • $\begingroup$ n is the length of binary strings, and m is how many there are. $\endgroup$ Commented Nov 22, 2024 at 20:20

1 Answer 1

Reset to default
2
$\begingroup$

Using KSetPartitions ResourceFunction.

Clear[fu]

fu[n_, m_] := 
 Select[Total[
    10^(ResourceFunction["KSetPartitions"][Range[n], m] - 
       1), {3}] /. (0 -> {}), GCD @@ # > 1 &]

Comparing with your first version of NonCoprimeList and T.

Length[fu @@ #] & /@ Tuples[Range[10], {2}]
T @@ # & /@ Tuples[Range[10], {2}] == %

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 19, 6, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 47, 98, 29, 0, 0, 0, 0, 0, 0, 1, 84, 280, 0, 0, 0, 0, 0, 0, 0,
1, 141, 650, 600, 120, 0, 0, 0, 0, 0}

True

Comparing performance on fresh kernel:

Length[fu @@ #] & /@ Tuples[Range[10], {2}]; // Timing
T @@ # & /@ Tuples[Range[10], {2}]; // Timing

{4.21875, Null}

{16.6719, Null}
Improve this answer
$\endgroup$
11
  • $\begingroup$ Thanks a lot. This is much more elegant than the messy code I came up with. $\endgroup$ Commented Nov 23, 2024 at 19:08
  • $\begingroup$ The code nevertheless generates all partitions and only then selects them based on GCD. This creates a huge array when we go to lengths n on the order of 13 or more, making things very slow. My idea with the code I was trying to write was to generate the partitions iteratively, i.e. defining the function for m using the same for m-1. This should speed up things a lot. $\endgroup$ Commented Nov 23, 2024 at 19:21
  • $\begingroup$ @Vosoni So you do not not care about the tuples only about how many of them there is? $\endgroup$ Commented Nov 23, 2024 at 19:30
  • $\begingroup$ I want to have the tuples too, but only those with GCD > 1. This is only quite a small fraction of all tuples. So I wanted to avoid generating a huge number of those that are coprime. $\endgroup$ Commented Nov 23, 2024 at 19:32
  • $\begingroup$ I don't think there is a way of getting their number without actually generating them. $\endgroup$ Commented Nov 23, 2024 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.