# Two cards which product is not a square

There are 100 cards on a table numbered 1,2,...,100. What is the maximum number of cards, which can be selected such that no two cards have a product, which is a perfect square?

Example: you cannot choose the cards with number 27 and 48, as $$27*48=81*16=36^2$$

The maximum is

61

Reasoning

We cannot choose two numbers whose square-free part is the same but any two numbers which have a square-free part which is different won't produce a square as a product. This means we could just choose all the numbers which are completely square-free (i.e, have no factor which is a square). This results in the following set
$$\{ 1,2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30,31,33,34,35,37,38,39,41,42,43,46,47,51,53,55,57,58,59,61,62,65,66,67,69,70,71,73,74,77,78,79,82,83,85,86,87,89,91,93, 94,95,97\}$$

• I had the same idea. I looked up the numbers on OEIS: A005117 – Jaap Scherphuis Dec 5 '19 at 15:04
• @JaapScherphuis Aha, I actually wrote this out by hand, really should have checked OEIS. – hexomino Dec 5 '19 at 15:05
• Is this a unique answer? Can we replace 1 with any perfect square like 4 etc., to get another set containing 61 elements that will serve as the answer? – ContraOpposite Dec 5 '19 at 22:45
• @ContraOpposite Yes, we could replace $1$ with any perfect square. Also, we could replace $2$ with any number of the form $2n^2$, etc. Overall, I think this means there are $10 \times 7 \times 5 \times 4^2 \times 3^3 \times 2^8 = 38707200$ different $61$-element solutions. – hexomino Dec 6 '19 at 10:07