Determine whether a number is 2017-friable without primes in your source code

Question

Out of all the years I've been making this challenge, 2017 is the first year that's been a prime number. So the question will be about prime numbers and their properties.

Your task is to produce a program or function that will take an arbitrarily large positive integer as input, and output or return whether or not the number is 2,017-friable — that is, whether the largest prime factor in that number is 2,017 or less.

---

Some example inputs and their outputs:

1 (has no prime factors)
true

2 (= 2)
true

80 (= 2 x 2 x 2 x 2 x 5)
true

2017 (= 2017)
true

2019 (= 3 x 673)
true

2027 (= 2027)
false

11111 (= 41 x 271)
true

45183 (= 3 x 15061)
false

102349 (= 13 x 7873)
false

999999 (= 3 x 3 x 3 x 7 x 11 x 13 x 37)
true

1234567 (= 127 x 9721)
false

4068289 (= 2017 x 2017)
true

Your program does not have to literally output true and false — any truthy or falsy values, and in fact any two different outputs that are consistent across true and false cases are fine.

---

However, you may not use any primes in your source code. Primes come in two types:

• Characters, or sequences of characters, that represent prime number literals.

  • The characters 2, 3, 5, and 7 are illegal in languages where numbers are valid tokens.

  • The number 141 is illegal because it contains 41, even though 1 and 4 are otherwise valid.

  • The characters B and D (or b and d) are illegal in languages where they are typically used as 11 and 13, such as CJam or Befunge.

• Characters that have prime-valued Unicode values, or contain prime-valued bytes in their encoding.

  • The characters %)+/5;=CGIOSYaegkmq are illegal in ASCII, as well as the carriage return character.

  • The character ó is illegal in UTF-8 because its encoding has 0xb3 in it. However, in ISO-8859-1, its encoding is simply 0xf3, which is composite and therefore okay.

The shortest code to do the above in any language wins.

Answer 1

Jelly, 8 bytes

44‘²!*ḍ@

Try it online! Note that test cases 11111 and above are a bit too much for TIO.

Verification

$ source="34,34,fc,82,21,2a,d5,40"
$ xxd -ps -r > 2017.jelly <<< $source
$ xxd -g 1 2017.jelly
0000000: 34 34 fc 82 21 2a d5 40                          44..!*.@
$ eval printf '"%d "' 0x{$source}; echo # Code points in decimal
52 52 252 130 33 42 213 64
$ test_cases="1 2 80 2017 2019 2027 11111 45183 102349 999999 1234567 4068289"
$ for n in $test_cases; do printf "%11d: %d\n" $n $(jelly f 2017.jelly $n); done
      1: 1
      2: 1
     80: 1
   2017: 1
   2019: 1
   2027: 0
  11111: 1
  45183: 0
 102349: 0

Test case 999999 has been running for 13 hours. I'm pessimistic about computing 2025!^4068289...

How it works

44‘²!*ḍ@  Main link. Argument: n

44        Yield 44.
  ‘       Increment to yield 45.
   ²      Square to yield 2025.
          Note that no integers in [2018, ..., 2025] are prime numbers.
    !     Take the factorial of 2025.
     *    Raise it to the n-th power.
          This repeats all prime factors in 2025! at least n times, so the result
          will be divisible by n if (and only if) all of its prime factors fall
          in the range [1, ..., 2025].
      ḍ@  Test the result for divisibility by n.

Answer 2

Jelly, 8 characters, 14 bytes of UTF-8

Æf½ṀḤ<90

Try it online!

Jelly normally uses its own codepage for programs. However, most of its prime-related builtins start with Æ, which is codepoint 13; not very helpful. Luckily, the interpreter also supports UTF-8, which has a friendlier encoding.

Verification

This program, in UTF-8, hexdumps like this:

00000000: c386 66c2 bde1 b980 e1b8 a43c 3930  ..f........<90

Verification that all the bytes are composite:

$ for x in c3 86 66 c2 bd e1 b9 80 e1 b8 a4 3c 39 30; do factor $((0x$x)); done
195: 3 5 13
134: 2 67
102: 2 3 17
194: 2 97
189: 3 3 3 7
225: 3 3 5 5
185: 5 37
128: 2 2 2 2 2 2 2
225: 3 3 5 5
184: 2 2 2 23
164: 2 2 41
60: 2 2 3 5
57: 3 19
48: 2 2 2 2 3

Verification that all the Unicode codepoints are composite:

$ perl -Mutf8 -E '$a = ord, print `factor $a` for split //, "Æf½ṀḤ<90"'
198: 2 3 3 11
102: 2 3 17
189: 3 3 3 7
7744: 2 2 2 2 2 2 11 11
7716: 2 2 3 643
60: 2 2 3 5
57: 3 19
48: 2 2 2 2 3

The only token parsed as a number is 90. None of 9, 0, and 90 are prime.

Explanation

The main mathematical insight here is that 45² is 2025, which neatly falls between 2017 (the current year) and 2027 (the next prime). Thus, we can take the square root of every prime factor of the number, and see if any exceeds 45. Unfortunately, we can't write 45 due to the literal 5, so we have to double it and compare to 90 instead.

Æf½ṀḤ<90
Æf        In the list of prime factors,
  ½       taking the square root of each element
   Ṁ      then taking the largest element
    Ḥ     and doubling it
     <90  produces a result less than 90.

Answer 3

Mathematica, 62 58 55 bytes

The last three bytes saved are totally due to Martin Ender!

#4<4||#<44*46&&#6[#^-1#4]&[Divisors[#][[6-4]],,,#,,#0]&

Unnamed function taking a positive integer argument and returning True or False.

Recursive algorithm, with #4<4 being the truthy base case (we only need it to return True on the imput 1, but the extra base cases are fine). Otherwise, we compute the second-smallest divisor (which is necessarily prime) of the input with Divisors[#][[6-4]]; if it's greater than 2024 (44*46) then we exit with False, otherwise we call the function recursively (using #6 set to #0) on the input divided by this small prime factor # (which we have to express as #^-1 times the input #4, since / is disallowed).

Structurally, the first half #4<4||#<44*46&&#6[#^-1#4]& is an anonymous function of six arguments, being called with arguments Divisors[#][[6-4]], Null, Null, #, Null, and #0; this is to get around the prohibition on the characters 2, 3, and 5.

Previous version, which saved four bytes by replacing 8018-6000 with 44*46, inspired by ais523's Jelly answer (Martin Ender also seemed inspired by an ais523 comment):

#<4||Divisors[#][[6-4]]<44*46&&#0[Divisors[#][[6-4]]^-1#]&

This was pretty nasty: I still don't know a way to actually set a variable in Mathematica under these restrictions! Both = and the e in Set are disallowed. Avoiding + and ) was also an issue, but not too hard to work around at the expense of more bytes.

Answer 4

Haskell, 48 47 bytes

\n->[snd$[product[1..44*46]^n]!!0`divMod`n]<[1]

Basically a translation of Dennis’ Jelly answer. xnor saved a byte.

Uses […]!!0 as parentheses because ) is banned, and snd + divMod because the m in mod and rem is banned.

Answer 5

Pyke, 10 8 7 9 bytes

P_Z|hwMX<

Try it here!

Saved 1 byte by using Dennis's way of generating 2025

P         -     factors(input)
 _        -    reversed(^)
  Z|      -   ^ or 0
    h     -  ^[0] or 1
        < - ^ < V
     wM   -  ⁴45 (ord("M")-32)
       X  -  ^**2

Answer 6

Actually, 9 bytes

τyM:44u²≥

Thanks to Dennis for lots of bytes!

Try it online!

Explanation:

τyM:44u²≥
τyM        largest prime factor of 2*input (doubled to deal with edge case of n = 1)
   :44u²   2025 (2027 is the next prime after 2017, so any number in [2017, 2026] can be used here - 2025 is very convenient)
        ≥  is 2025 greater than or equal to largest prime factor?

Answer 7

Mathematica, 66 74 bytes

Thanks to Dennis for pointing out that U+F4A1 is prohibited.

Fold[Function[{x,d},And[x,Tr[Divisors@d^0]>6-4||d<44*46]],0<1,Divisors@#]&

Explanation:

Divisors@#: List of integer divisors of the first argument #.

0<1: Golf for True (also avoids the use of the letter e).

Divisors@d^0: List of the form {1, 1, ..., 1} with length equal to the number of divisors of d.

Tr: For a flat list, Tr returns the sum of that list. Thus Tr[Divisors@d^0] returns the number of divisors of d.

Function[{x,d},And[x,Tr[Divisors@d^0]>6-4||d<44*46]]: Anonymous function with two arguments x and d. The idea is that d is a divisor of # and we test to see if it is either composite or less than or equal to 2017 (inclusive). 2017-friability is equivalent to all the divisors satisfying this condition. As ais523 discovered, being a prime less than or equal to 2017 is equivalent to being a prime less than 2025. As Greg Martin pointed out, it suffices to test whether it is less than 2024=44*46. The argument x acts as an accumulator for whether all of the divisors encountered so far satisfy this property. We then left Fold this function through all of the divisors of # with starting value True, since we have access to neither Map nor /@.

Answer 8

Brachylog, 9 10 bytes

*$ph$r*<90

Try it online!

Basically using the same algorithm as my other answer. $ph finds the first (h) prime factor ($p); this is the largest prime factor, as Brachylog's prime factor lists go from largest to smallest. Then I take the square root ($r), double (*), and test to see if it's less than 90 (<90).

I had to double the input first because 1 has no prime factors (and thus no first prime factor). This adds an extra prime factor of 2, which can't affect whether a number is 2017-friable, but prevents a failure when handling 1.

Answer 9

05AB1E, 10 bytes

fθ46n99-›È

Returns 1 if true, 0 otherwise.

Try it online!

Explanation

f          # Push the list of prime factors (ordered)
 θ         # Get the last element
  46n99-   # Push 2017 (46² - 99)
        >  # Push 1 if the last prime factor is greater than 2017, 0 otherwise
         È # Is the resulting number even ? Transforms 1 to 0 and 0 to 1.
           # Implicit display

Answer 10

MATL, 15 bytes

t:\~ftZp*44QU<A

Outputs 0 for non-2017-friable or 1 for 2017-friable.

Try it online! Or verify all test cases.

This program checks that all bytes are composite.

Explanation

t       % Implicit input n. Duplicate
:       % Range [1 2 ... n]
\       % Modulo. Gives 0 for divisors of n
~f      % Indices of zero values
t       % Duplicate
Zp      % Is-prime. Gives 1 for primes, 0 for composites
*       % Multiply
44QU    % 44, add 1, square: 2025
<       % Less than, element-wise
A       % True (1) if all entries are nonzero

Answer 11

Bash, 144 bytes

ASCII encoding:

{
printf '[ '
`tr D-Z _-z <<<KFH`tor $1|tr -d :|`tr B-Z _-z <<<JUH`p -o '[0-9]*$'
printf ' -lt $[24*86-46] ]'
}|tr \\n \ |`tr B-Z _-z <<<EDVK`

As usual for shell, the exit code indicates success (0) or failure (non-0).

This is effectively a different spelling of

[ factor $1|tr -d :|grep -o '[0-9]*$' -lt 2018 ]

We get the largest factor with factor $1|grep -o '[0-9]*$'; the tr -d : is to special-case for input = 1.

The expression $[6*6*69-466] evaluates to 2018.

It was tricky to use tr for the command names and still use command substitution - I couldn't use the nesting form $( ), so I ended up piping into another Bash to evaluate the result.

Test results:

$ for i in 1 2 80 2017 2019 2027 11111 45183 102349 999999 1234567 4068289; do printf '%d %s\n' $i `./105241.sh $i  && echo true || echo false`; done
1 true
2 true
80 true
2017 true
2019 true
2027 false
11111 true
45183 false
102349 false
999999 true
1234567 false
4068289 true

Confirmation of character codes:

$ grep -v '^#' ./105241.sh | perl -n -Mutf8 -E '$a = ord, print `factor $a` for split //, $_' | grep -v ': .* ' | wc -l
0

Answer 12

Pyth, 11 bytes

!s>R^h44h1P

Try it online. Test suite.

Uses Dennis's trick to get 2025, then checks if no prime factors of input are greater.

Answer 13

Julia 0.4, 84 38 37 bytes

n->1^n:44*46|>prod|>t->t^n-t^n÷n*n<1

Expects a BigInt as argument.

Try it online! or verify that no byte is prime.

Answer 14

Japt, 14 bytes

k æ¨44*46 ?0:1

Returns 1 if true, 0 if false.

Try it here.

Answer 15

Braingolf, 11 bytes [very non-competing]

VRp#ߢ-?0:1

Try it online!

Unreadable due to the ߢ which screws with the numbers, however still works in an interpreter.

I didn't even notice the character restrictions when I wrote this, but all I had to do was change the weird unicode character from 2017 to 2018.

Given 2018 is not a prime, any prime <= 2018 is also <= 2017

Explanation

VRp#ߢ-?0:1  Implicit input from command-line args
VR            Create stack2, return to stack1
  p           Split last item into prime factors, push each one to stack in asc order
   #ߢ         Push 2018
     -      Subtract last 2 items (highest prime factor - 2017)
      ?     If last item > 0..
       0    ..push 1
        :   Else..
         1  ..Push 1
            Implicit output of last item on stack