I am having difficulty finding the exact Big O notation for the size of the search space of OEIS A015617 as a function of n. I am researching a theory that A015617 may have useful applications in cryptography. you can see that this is a subset of A000292. more precisely, A015617 and A000292 are the size (Big O) of the set defined by n and the procedure to generate the permutations that meet some conditions. A000292 and A015617 are themselves Big O notation but they do not explicitly show the permutations of the original set. to find the original sets you can use mathematica code examples here
n = 5
fullset_A000292 = Subsets[Range[n], {3}]]
fullset_A015617 = Select[Subsets[Range[n], {3}], Apply[CoprimeQ]]
It should be obvious then that elements of fullset_A000292 that are not in fullset_A015617 have at least 1 common factors in 2 or more members of {a,b,c} that makes them easier to reduce the Big O of A000292 compared to A015617 which is presumed to be irreducible in computational complexity. I have attempted to approximate some guesses that fit the function with a graph to show the results
a = 140
f = Table[Length[Subsets[Range[x], {3}]], {x, 3, a}]
g = Table[Length[Select[Subsets[Range[x], {3}], Apply[CoprimeQ]]], {x, 3, a}]
e = Table[Floor[(x/2.7)^3], {x, 3, a}]
d = Table[Floor[((x - (x/Log[x]))/2.2)^3 - (x^2)/3], {x, 3, a}]
FindGeneratingFunction[f, x]
(*FindGeneratingFunction[g,x] this has been commented out because mathematica fails to give an answer*)
ListLinePlot[{f, g, d, e}]
as you can see mathematica fails to find a function that fits the discrete function returned and stored in g. e, d are found by trial and error. they are my best guesses but they are not in any way rigorous. Can you help me find the generating function that best fits the plot of A015617? is there a rigorous upper bound and a rigorous lower bound for A015617 with proof? would this be a problem that can be solved using linear regression and gradient descent with AI assuming that the model e or d would be suitable? what is the method for determining if the generating function will intersect or not intersect A015617? is this simply a difficult problem on the order of PNT n/ln(n)? not solvable? I see the Legendre correction constant to the PNT is -1.08366 which makes me think that gradient descent for linear regression may actually return numbers that are not integers or logs of integers. This is somewhat encouraging although completely mysterious to me intuitively. Help or comments of any sort are greatly appreciated.
Note that A000292 is an nCr function with known Big O notation therefor A000292 has already been solved.