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

41

1

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.

Joe Z.

Posted 2017-01-01T00:00:19.757

Reputation: 30 589

Side note: "friable" is an improvement being adopted over the old-and-undescriptive "smooth" in this context. – Greg Martin – 2017-01-01T00:06:58.907

@GregMartin Done. – Joe Z. – 2017-01-01T00:18:39.247

1Do truthy and falsy values need to be consistent? Or can they vary as long as they are truthy or falsy? – Luis Mendo – 2017-01-01T01:10:50.800

10The lack of = rules out most standard languages... – Neil – 2017-01-01T01:12:38.750

@LuisMendo They need to be consistent, yes. One output for true, another for false. – Joe Z. – 2017-01-01T01:22:41.570

This may be handy to check if characters are prime when encoded in ASCII. Just paste your code (one line) as input. The result should be all zeros – Luis Mendo – 2017-01-01T02:07:41.573

4-1 for a do X without Y challenge. It's really quite trivial hidden behind a rather unnecessary set of character restrictions – Downgoat – 2017-01-02T02:06:17.743

Why is tab illegal? Its ASCII value is 9. Are you perhaps thinking of vertical tab (11), which no one ever uses? – jwodder – 2017-01-02T02:42:03.233

Yes, I meant vertical tab. Looks like I misunderstood the purpose of that character when I read about it. – Joe Z. – 2017-01-02T03:51:53.757

@Downgoat I'm actually surprised the downvote-to-upvote ratio is so small myself. I thought given all the talk about my first New Year's Puzzle being a broken window that nobody would appreciate a challenge like this one anymore. But thankfully it seems like it's unique enough to be good, since some the answers like Dennis's are actually doing some pretty clever stuff. – Joe Z. – 2017-01-02T03:55:23.910

1I don't like the part about them being arbitrarily large. It would be better if they went up to 2^31-1. – Bijan – 2017-03-16T21:13:38.297

I think the the test case 1234567 is wrong, 9721 is bigger than 2017 – Embodiment of Ignorance – 2019-04-25T03:41:30.017

Answers

37

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.

Dennis

Posted 2017-01-01T00:00:19.757

Reputation: 196 637

23You are cruel to numbers. :) – Greg Martin – 2017-01-01T09:55:54.320

3@GregMartin bah. I've seen an answer (in a different language) where an input of size 6 would hog the memory for several hours, then crash. I'll just say: (2^n)!. This also crahes for six-sized inputs, but at least the inputs are in a decimal alphabet rather than a binary one. – John Dvorak – 2017-01-01T12:45:18.920

Isn't this 13 bytes? Dennis you have so much reputation that I'm sure I'm the one making a mistake here hahah – Albert Renshaw – 2017-01-30T03:15:58.717

7

@AlbertRenshaw It would indeed be 13 bytes in UTF-8, but Jelly uses a custom code page that encode all characters it understands as a single byte each.

– Dennis – 2017-01-30T03:38:37.497

3@Dennis knew there'd be an explanation; very cool to learn about, thanks! – Albert Renshaw – 2017-01-30T03:40:57.973

11

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.

user62131

Posted 2017-01-01T00:00:19.757

Reputation:

2Doesn't Jelly require a flag (1 byte) to use UTF-8? – Luis Mendo – 2017-01-01T01:18:19.200

@LuisMendo: The command-line interpreter does, but the interpreter at Try It Online! is configured differently and doesn't require it. So this is just a case of picking the interpreter that interprets your program the way you want. (In any case, the flag in question, u, is composite, so it'd just be a matter of changing the score rather than something that invalidates it.) – None – 2017-01-01T01:42:31.450

10

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.

Greg Martin

Posted 2017-01-01T00:00:19.757

Reputation: 13 940

You could perhaps set a lambda parameter rather than a variable. (That said, #2 would also be disallowed, so you'd have to be careful with how your lambdas nested, and the lack of parentheses might make that difficult.) – None – 2017-01-01T01:44:03.850

Implementing @ais523's suggestion saves three bytes: #4<4||#<44*46&&#6[#^-1#4]&[Divisors[#][[6-4]],,,#,,#0]& throws a bunch of warnings because it now tries Divisors[#][[2]] before ensuring that the input is greater than 1 (or 3), but the result is still correct. – Martin Ender – 2017-01-02T11:56:06.667

Oh man, that's freaking cunning. – Greg Martin – 2017-01-02T19:16:36.340

7

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.

Lynn

Posted 2017-01-01T00:00:19.757

Reputation: 55 648

Nice trick with the divMod! I think you can replace the !!0<1 with <[1]. But it looks it it's shorted to use div as [\p n->p^n`div`n*n>p^n-1]!!0$product[1..44*46]. – xnor – 2017-01-02T02:32:23.863

There's also \n->[0|p<-[product[1..44*46]^n],0<-[p,p-n..0]], which uses that outputs need only to be consistent. – xnor – 2017-01-02T02:58:43.157

@xnor Feel free to post those as separate answer(s), I think they’re sufficiently different from mine ^^ – Lynn – 2017-01-02T14:46:55.287

6

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

Blue

Posted 2017-01-01T00:00:19.757

Reputation: 26 661

5

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?

Mego

Posted 2017-01-01T00:00:19.757

Reputation: 32 998

5

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 /@.

ngenisis

Posted 2017-01-01T00:00:19.757

Reputation: 4 600

1Way to fight through the restrictions! – Greg Martin – 2017-01-01T09:57:50.543

5

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.

user62131

Posted 2017-01-01T00:00:19.757

Reputation:

2

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

Kaldo

Posted 2017-01-01T00:00:19.757

Reputation: 1 135

Welcome to PPCG! – Martin Ender – 2018-01-08T16:50:20.930

1

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

Luis Mendo

Posted 2017-01-01T00:00:19.757

Reputation: 87 464

1

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

Toby Speight

Posted 2017-01-01T00:00:19.757

Reputation: 5 058

0

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.

PurkkaKoodari

Posted 2017-01-01T00:00:19.757

Reputation: 16 699

0

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.

Dennis

Posted 2017-01-01T00:00:19.757

Reputation: 196 637

0

Japt, 14 bytes

k æ¨44*46 ?0:1

Returns 1 if true, 0 if false.

Try it here.

Oliver

Posted 2017-01-01T00:00:19.757

Reputation: 7 160

k has a prime value – Embodiment of Ignorance – 2019-04-26T02:54:20.493

0

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

Skidsdev

Posted 2017-01-01T00:00:19.757

Reputation: 9 656