8
\$\begingroup\$

Create the shortest function, program, or expression that calculates a sequence of squarefree palindromic numbers.

A squarefree number is one which is not evenly divisible by a square number (i.e. does not contain a repeated prime factor). For example, \$44 = 2^2 \times 11\$ is not squarefree, whereas \$66 = 2\times3\times11\$ is.

You can find a list of the numbers from this link. The list goes as such: 1, 2, 3, 5, 6, 7, 11, 22, 33, 55, 66, 77, 101, 111, 131, 141, 151, 161, 181, 191...

\$\endgroup\$
  • 3
    \$\begingroup\$ @user The challenge does say Create the shortest function, program, or expression. An expression is not a standard format for code-golf, however. \$\endgroup\$ – Arnauld Dec 18 '20 at 19:10
  • 1
    \$\begingroup\$ Am I missing something in the terminology here? If it's a prime factorization, all the factors must be primes. Thus, none of them can be a square. I think I understand what's being sought here (no two identical prime factors), but it should be stated explicitly. \$\endgroup\$ – Xcali Dec 18 '20 at 19:44
  • 1
    \$\begingroup\$ @user, then the question is different: What palendromic numbers are not perfect squares? \$\endgroup\$ – Xcali Dec 18 '20 at 19:46
  • 5
    \$\begingroup\$ I've edited the question slightly to include the definition of a squarefree number, as well as examples. However, until you define "calculates a sequence of", this is still unclear. I'd recommend going by our standard sequence rules \$\endgroup\$ – caird coinheringaahing Dec 18 '20 at 20:48
  • 2
    \$\begingroup\$ I'm not clear, does the sequence need to list every squarefree palindrome, or just be any infinite sequence of such numbers, presumably distinct? \$\endgroup\$ – xnor Dec 18 '20 at 21:29
4
\$\begingroup\$

Python 2, 82 75 bytes

n=0
while 1:
 n+=1
 if`n`[::-1]==`n`*all(n%i**2for i in range(2,n)):print n

Try it Online!

If this was a decision problem (54 bytes):

lambda n:`n`[::-1]==`n`*all(n%i**2for i in range(2,n))

Explanation:

`n`[::-1]==`n`                     # If n is a palindrome. `n` is repr(n).
                                   # We check that it's the same
                                   # backwards and forwards.
              *                    # Multiplplying 2 booleans is AND
all(n%i**2for i in range(2,n))     # Check that squares of all #'s < n do not divide n
\$\endgroup\$
  • \$\begingroup\$ Your condition can be shortened to `n`[::-1]==`n`*all(n%i**2for i in range(2,n)). \$\endgroup\$ – ovs Dec 18 '20 at 22:25
  • \$\begingroup\$ @ovs Nice one! Thanks. \$\endgroup\$ – mbomb007 Dec 18 '20 at 22:34
1
\$\begingroup\$

Wolfram Language (Mathematica), 52 bytes

Do[If[SquareFreeQ@n&&PalindromeQ@n,Print@n],{n,∞}]

Try it online!

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 8 bytes

Prints the infinite sequence.

∞ʒÂQyÓà*

Try it online!

Commented:

∞        # push the list of natural numbers [1, 2, ...]
 ʒ       # keep the values for which the following is 1:
  Â      #   push the number and its reverse
   Q     #   are both equal?
    y    #   push the number again
     Ó   #   push the exponents of the prime factorisation
      à  #   take the maximum
       * #   multiply both numbers
\$\endgroup\$
1
\$\begingroup\$

Husk, 8 bytes

foS=upİ↔

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Brachylog, 5 bytes

Generates the sequence

ḋ≠&↔?

Try it online!

ḋ≠&↔? (the input's)
ḋ     prime decomposition
 ≠    has only unique elements
  &   and the input
   ↔  reversed
    ? is the input
      (and also the output)
\$\endgroup\$
0
\$\begingroup\$

Jelly, 10 bytes

1ÆfQƑ׌ḂƲ#

Try it online!

Returns the first n squarefree palindromes

How it works

1ÆfQƑ׌ḂƲ# - Main link. Takes no arguments
        Ʋ  - Group the previous 4 links into a monad f(k):
 Æf        -   Prime factorisation of k (with repeats)
    Ƒ      -   Is this invariant under:
   Q       -     Deduplication
      ŒḂ   -   Is k a palindrome?
     ×     -   Both conditions are true?
1        # - Read an integer n from STDIN. Count up k = 1, 2, 3, ...
             until n such k return true under f(k). Return those k
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES7),  81  76 bytes

Returns the n-th term, 1-indexed.

f=(n,i)=>(g=d=>i[d]&&i[d]-i[k++]?1:i%d--**2?g(d):d)(i+=k='')||n--?f(n,-~i):i

Try it online!

Commented

Helper function

The helper function g checks simultaneously whether i is palindromic and squarefree. The variable d is used as a counter to test the divisors and as a decreasing digit index. The variable k is used as an increasing digit index. Both i and k are defined in the wrapper.

g = d =>            // g is a recursive function taking a counter d
  i[d] &&           //   if i[d] is defined
  i[d] - i[k++] ?   //   and it's not equal to i[k] (increment k afterwards):
    1               //     i is not palindromic: force a truthy result
  :                 //   else:
    i % d-- ** 2 ?  //     if d² is not a divisor of i (decrement d afterwards):
      g(d)          //       do a recursive call
    :               //     else:
      d             //       return d (0 if i is squarefree)

Wrapper

The main function decrements n whenever g returns 0 and stops when n = 0.

f = (n, i) =>       // f is a recursive function taking an index n
  g(i += k = '') || //   set k to a zero'ish empty string,
                    //   coerce i to a string
                    //   and invoke g with d = i
  n-- ?             //   if the above call was truthy or n is not equal to 0:
    f(n, -~i)       //     do a recursive call with i + 1
  :                 //   else:
    i               //     success: return i
\$\endgroup\$
0
\$\begingroup\$

Perl 5 -MList::Util=all, 52 bytes

$_-$r||(all{$r%$_**2}2..$_)&&say while$r=reverse++$_

Try it online!

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.