text:
Tweetable hash function challenge
In this code-challenge you will write a hash function in 140 bytes1 or less of source code. The hash function must take an ASCII string as input, and return a 24-bit unsigned integer ([0, 224-1]) as output.
Your hash function will be evaluated for every word in this large British English dictionary2. Your score is the amount of words that share a hash value with another word (a collision).
The lowest score wins, ties broken by first poster.
Test case
Before submitting, please test your scoring script on the following input:
duplicate
duplicate
duplicate
duplicate

If it gives any score other than 4, it is buggy.

Clarifying rules:

Your hash function must run on a single string, not a whole array. Also, your hash function may not do any other I/O than the input string and output integer.
Built-in hash functions or similar functionality (e.g. encryption to scramble bytes) is disallowed.
Your hash function must be deterministic.
Contrary to most other contests optimizing specifically for the scoring input is allowed.

1 I am aware Twitter limits characters instead of bytes, but for simplicity we will use bytes as a limit for this challenge.
2 Modified from Debian's wbritish-huge, removing any non-ASCII words.

Are seeded rand functions allowed, or are they considered "similar functionality"?

@Doorknob I would consider them similar functionality. It is intended you scramble the input using your own code, and not through some side effect of other hashing algorithms, crypto, rng, compression, etc.

Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch's ? What the...?

@DonMuesli https://en.wikipedia.org/wiki/Llanfairpwllgwyngyll (fun fact: that word is also in Jelly's built-in compression dictionary)

Relevant: http://140byt.es/

@orlp What domain does the hash function have to be defined on? Is it only required to work for words in the dictionary? Or does it have to work with inputs not in that dictionary as well?

This is a lovely challenge!

I think you should disallow built-in dictionaries.

Per the spec in the question, a valid hash should cover the inclusive range  [0, 2**24-1], but your own submission uses %(2**24-1), which covers the range [0, 2**24-2], since n%n (in this case n is 2**24-1) returns 0. Could you clarify the challenge's specifications more, please?

I estimate that a random oracle would score around 6832 on this challenge. Anything better than that has to be optimized for the dictionary used for scoring. Any decent hash function will score around the same value. There will be some variation in score depending on the exact constants used in the hashing algorithm, thus it is possible to do a little better than 6832, but if you want to do significantly better than that, you have to an approach that is much more targeted towards the specific dictionary.

For reference: Taking the 24 MSB of SHA-512 would achieve a score of 6816.

@Dennis I interpret built-in dictionaries as being disallowed by clarifying rule #1. I consider that to be extra I/O, as you're reading a nontrivial amount of extra information outside of the input string.

@kasperd That's correct, this challenge however is not about finding a generic hash function, it's about finding a perfect hash function.

@mbomb007 That's a mistake, my submission had a bug. The specs are still authoritative.

@kasperd It's not required that the hash function works on elements not inside the dictionary, although I don't see why that would matter for any valid implementation (dictionary lookups are considered extra I/O, even when the dictionary is a builtin in your language).

@orlp If the function is only required to work for words in the dictionary, then the modulus operation in your answer is redundant.

Not going to post as an answer because it definitely should be disallowed (the hash function should not use mutable global state, or something like that), but I had some fun writing this: H=lambda s,i=[1],d={}:d[s] if s in d else (i[0],d.__setitem__(s,i[0]),i.__setitem__(0,i[0]+1))[0] - score is 0.

@Random832 Global state is considered extra I/O.

@orlp That's an unreasonable definition of "I/O". You're not reading it, you're maintaining it in memory. The text of the clarification isn't sufficient to conclude that "I/O" is meant to include things that are not I/O. The text of the clarification is clearly targeted at hash functions that open the file again themselves.

Some back-of-the-envelope calculations: With D=340275 words and R=2^24 hash outputs, a random hash has an expected D^2/(2*R) = 3450 colliding pairs, some of which overlap. There are an expected D^3/(6*R^2) = 23 colliding triples and a negligible number of larger collisions, which means these triples are likely disjoint. This gives an expected 6829 words that share a hash value, ~70 in triples and the rest in pairs. The standard deviation is estimated at 118, so getting <6200 with a random hash is roughly a 5 sigma event.

@Random832 A hash function is supposed to produce the same output each time it is given the same input. That needs to be true even across invocations of the program. So after the program has been stopped and started again, your hash function still needs to reproduce the same hash output given the same input. That means the global state cannot help you, because you are required to give the same result, even when given a new clean version of the global state.

@orlp The point of my calculations was to reason about what was needed for an entry to be competitive. Those calculations lead me to the conclusion, that a generic hash function cannot be competitive, not even if you tweak the parameters. So if I wanted a better score, I would have to do something else (which I did). And the calculation also shows that any answer with a generic hash function and a score less than 6000 is essentially guaranteed to be flawed.

@xnor Those numbers appear to be consistent with my rough estimate in an earlier comment. Nice to know the standard deviation as well. With those numbers I can be even more confident when I point out answers with an unrealistic score.

3 of spades! Yay!

@kasperd You're misinterpreting the question. You can do significantly better than the random oracle, and that's the point of this question. Please read up on perfect hash functions. This question is not about generic hash functions.

@orlp You are totally not getting the point. There have been numerous answers providing a generic hash function with no targeting for the specific dictionary which still claimed a score in the ballpark around 3600. As long as the answer is a generic hash function where you have perhaps tweaked some of the parameters you will get a score within a few standard deviations of the expected value, there is no way such an entry can score less than 6000.

@kasperd All right, I haven't seen those answers, so I was unaware of that.

@orlp That's probably because each time it happens there is somebody around to point it out in comments, and the answer gets fixed or deleted. It has happened frequently enough that the question even got edited to warn about it. Not that it helped, I have seen at least 3 of them after the warning was added to the question.

Oh cool, my generic hash function comes to 6825, so slightly better than expected. But given the other contenders, I’m not bothering to reimplememnt it in a short language (I used the shell implementation for easiness of testing).

@mirabilos If you feel your code can be golfed to within the limit, you may submit a link with the same for someone else to do so.

Alright fine I’ll go learn a golfing language.
CJam, 140 bytes, 3314 colliding words
00000000: 7b5f 3162 225e d466 4a55 a05e 9f47 fc51  {_1b"^.fJU.^.G.Q
00000010: c45b 4965 3073 72dd e1b4 d887 a4ac bcbd  .[Ie0sr.........
00000020: 9c8f 70ca 2981 b2df 745a 10d0 dfca 6cff  ..p.)...tZ....l.
00000030: 7a3b 64df e730 54b4 b068 8584 5f6c 9f6b  z;d..0T..h.._l.k
00000040: b7f8 7a1f a2d3 b2b8 bcf5 cfa6 1ef7 a55c  ..z............\
00000050: dca8 795c 2492 dc32 1fb6 f449 f9ca f6b7  ..y\$..2...I....
00000060: a2cf 4772 266e ad4f d90c d236 b51d c5d5  ..Gr&n.O...6....
00000070: 5c46 3f9b 7cb4 f195 4efc fe4a ce8d 9aee  \F?.|...N..J....
00000080: 9dbc 223d 6962 3443 2329 257d            .."=ib4C#)%}

Defines a block (anonymous function).  To test, you could add qN%%N*N to take the newline-separated list of words on stdin and write a newline-separated list of hashes on stdout.  Equivalent Python code:
b=lambda s,a:reduce(lambda n,c:n*a+ord(c),s,0)
f=lambda s:b(s,ord('^\xd4fJU\xa0^\x9fG\xfcQ\xc4[Ie0sr\xdd\xe1\xb4\xd8\x87\xa4\xac\xbc\xbd\x9c\x8fp\xca)\x81\xb2\xdftZ\x10\xd0\xdf\xcal\xffz;d\xdf\xe70T\xb4\xb0h\x85\x84_l\x9fk\xb7\xf8z\x1f\xa2\xd3\xb2\xb8\xbc\xf5\xcf\xa6\x1e\xf7\xa5\\\xdc\xa8y\\$\x92\xdc2\x1f\xb6\xf4I\xf9\xca\xf6\xb7\xa2\xcfGr&n\xadO\xd9\x0c\xd26\xb5\x1d\xc5\xd5\\F?\x9b|\xb4\xf1\x95N\xfc\xfeJ\xce\x8d\x9a\xee\x9d\xbc'[b(s,1)%125]))%(8**8+1)

Pyth, 140 bytes, 3535 3396 colliding words
00000000: 4c25 4362 2d68 5e38 2038 2a36 3643 4022  L%Cb-h^8 8*66C@"
00000010: aa07 f29a 27a7 133a 3901 484d 3f9b 1982  ....'..:9.HM?...
00000020: d261 79ab adab 9d92 888c 3012 a280 76cf  .ay.......0...v.
00000030: a2e5 8f81 7039 acee c42e bc18 28d8 efbf  ....p9......(...
00000040: 0ebe 2910 9c90 158e 3742 71b4 bdf5 59c2  ..).....7Bq...Y.
00000050: f90b e291 8673 ea59 6975 10be e750 84c8  .....s.Yiu...P..
00000060: 0b0f e7e8 f591 f628 cefa 1ab3 2e3c 72a3  .......(.....<r.
00000070: 7f09 6190 dbd2 d54e d6d0 d391 a780 ebb6  ..a....N........
00000080: ae86 2d1e 49b0 552e 7522 4362            ..-.I.U.u"Cb

Defines a function named y.  To test, you could add jmyd.z to take the newline-separated list of words on stdin and write a newline-separated list of hashes on stdout.  Equivalent Python code:
b=lambda s,a:reduce(lambda n,c:n*a+ord(c),s,0)
f=lambda s:b(s,256)%(8**8+1-66*ord("\xaa\x07\xf2\x9a'\xa7\x13:9\x01HM?\x9b\x19\x82\xd2ay\xab\xad\xab\x9d\x92\x88\x8c0\x12\xa2\x80v\xcf\xa2\xe5\x8f\x81p9\xac\xee\xc4.\xbc\x18(\xd8\xef\xbf\x0e\xbe)\x10\x9c\x90\x15\x8e7Bq\xb4\xbd\xf5Y\xc2\xf9\x0b\xe2\x91\x86s\xeaYiu\x10\xbe\xe7P\x84\xc8\x0b\x0f\xe7\xe8\xf5\x91\xf6(\xce\xfa\x1a\xb3.<r\xa3\x7f\ta\x90\xdb\xd2\xd5N\xd6\xd0\xd3\x91\xa7\x80\xeb\xb6\xae\x86-\x1eI\xb0U.u"[b(s,256)%121]))

Theoretical limits
How well can we expect to do?  Here is a plot of x, the number of colliding words, vs. y, the entropy in bytes required to get at most x colliding words.  For example, the point (2835, 140) tells us that a random function gets at most 2835 colliding words with probability 1/256**140, so it’s exceedingly unlikely that we’ll ever be able to do much better than that with 140 bytes of code.

Nice analysis of the theoretical limits. In order to beat that theoretical limit one would probably have to use a language with builtin functions optimized for the dictionary in the question (which would be cheating). If the language has a builtin cryptographic hash, the limit can be turned into a more-or-less constructive method for finding an optimal solution. Consider this: $h(w || c) % 2^{24}$ where $c$ is a byte string constant. In a random oracle model that could be shown to get close to the optimum with high probability. Of course brute forcing the $c$ would not be feasible.

How did you calculate the formula for the graph? Really interesting!

@NikoNyrh Dynamic programming. Let (w, c, h) represent a state with w words, of which c are colliding with h distinct hashes, and the remaining w − c all have distinct hashes. If we add a random word, the state becomes (w + 1, c, h) with probability 1 − (h + w − c) / 2^24, or (w + 1, c + 1, h) with probability h / 2^24, or (w + 1, c + 2, h + 1) with probability (w − c) / 2^24. Then the final entropy graphed with x colliding words is the log base 1/256 of the sum of probabilities at states (340275, c, h) with c ≤ x.

I can’t believe no one has asked how you came up with the hash function?  I would be very interested to know.

Python, 5333 4991
I believe this is the first contender to score significantly better than a random oracle.
def H(s):n=int(s.encode('hex'),16);return n%(8**8-ord('+%:5O![/5;QwrXsIf]\'k#!__u5O}nQ~{;/~{CutM;ItulA{uOk_7"ud-o?y<Cn~-`bl_Yb'[n%70]))

Sorcery! def H(s):n=int(s.encode('hex'),16);return n%... saves 5 bytes, in case you can use them somehow...

@Dennis I could have used 5 bytes to make the string constant 5 bytes longer. But I would have to start over building the string constant from scratch if I change the length. And I am not sure those 5 bytes will give me enough improvement that it is worth starting over building the string. I have spend hours of CPU time optimizing the string constant already.

@Dennis I guess a few extra bytes would give me the freedom to use some characters in the constant needing escaping. That way I could potentially use a few extra bytes without having to construct the string all over again.

If you want another byte, 2**24 == 8**8.

Python 2, 140 bytes, 4266 colliding words
I didn’t really want to start with the non-printable bytes thing given their unclear tweetability, but well, I didn’t start it.  :-P
00000000: efbb bf64 6566 2066 2873 293a 6e3d 696e  ...def f(s):n=in
00000010: 7428 732e 656e 636f 6465 2827 6865 7827  t(s.encode('hex'
00000020: 292c 3336 293b 7265 7475 726e 206e 2528  ),36);return n%(
00000030: 382a 2a38 2b31 2d32 3130 2a6f 7264 2827  8**8+1-210*ord('
00000040: 6f8e 474c 9f5a b49a 01ad c47f cf84 7b53  o.GL.Z........{S
00000050: 49ea c71b 29cb 929a a53b fc62 3afb e38e  I...)....;.b:...
00000060: e533 7360 982a 50a0 2a82 1f7d 768c 7877  .3s`.*P.*..}v.xw
00000070: d78a cb4f c5ef 9bdb 57b4 7745 3a07 8cb0  ...O....W.wE:...
00000080: 868f a927 5b6e 2536 375d 2929            ...'[n%67]))

Python 2, 140 printable bytes, 4662 4471 4362 colliding words
def f(s):n=int(s.encode('hex'),16);return n%(8**8+3-60*ord('4BZp%(jTvy"WTf.[Lbjk6,-[LVbSvF[Vtw2e,NsR?:VxC0h5%m}F5,%d7Kt5@SxSYX-=$N>'[n%71]))

Inspired by the form of kasperd’s solution, obviously—but with the important addition of an affine transformation on the modulus space, and entirely different parameters.

+1 I am not giving up without a fight. But I think I have to stop optimizing my current solution and find another approach, because I am not going to beat you if I keep using my current approach to optimizing the parameters. I'll be back with an edit to my solution once I have beaten yours....

@kasperd: Awesome, bring it on. :-P

@AndersKaseorg How do you find the string?

@AndersKaseorg I managed to speed up my parameter search a lot. And I removed an obstacle which was causing my search to get stuck on suboptimal solutions. But I still couldn't make it any better than 4885. After some pondering on why I couldn't make it any further I suddenly realized what is wrong with my solution and how it can be fixed. Now the affine transformation in your solution makes perfect sense to me. I think the only way I can possibly catch up is by using an affine transformation myself.

@kasperd: Very nice. When searching for a better string in n%(8**8-ord('…'[n%70])) without other parameter changes, I had only managed to get to 4995, so it looks like your new optimizer has caught up to mine. Now this gets more interesting!

@AndersKaseorg I am crunching through the parameter space for a different affine transformation. You are still 47 points ahead of me, but I count on a few hours of CPU time changing that.

CJam, 4125 3937 3791 3677
0000000: 7b 5f 39 62 31 31 30 25 5f 22 7d 13 25 77  {_9b110%_"}.%w
000000e: 77 5c 22 0c e1 f5 7b 83 45 85 c0 ed 08 10  w\"...{.E.....
000001c: d3 46 0c 5c 22 59 f8 da 7b f8 18 14 8e 4b  .F.\"Y..{....K
000002a: 3a c1 9e 97 f8 f2 5c 18 21 63 13 c8 d3 86  :.....\.!c....
0000038: 45 8e 64 33 61 50 96 c4 48 ea 54 3b b3 ab  E.d3aP..H.T;..
0000046: bc 90 bc 24 21 20 50 30 85 5f 7d 7d 59 2c  ...$! P0._}}Y,
0000054: 4a 67 88 c8 94 29 1a 1a 1a 0f 38 c5 8a 49  Jg...)....8..I
0000062: 9b 54 90 b3 bd 23 c6 ed 26 ad b6 79 89 6f  .T...#..&..y.o
0000070: bd 2f 44 6c f5 3f ae af 62 9b 22 3d 69 40  ./Dl.?..b."=i@
000007e: 62 31 35 32 35 31 39 25 31 31 30 2a 2b 7d  b152519%110*+}

This approach divides domain and codomain into 110 disjoint sets, and defines a slightly different hash function for each pair.
Scoring / Verification
$ echo $LANG
en_US
$ cat gen.cjam
"qN%{_9b110%_"
[125 19 37 119 119 34 12 225 245 123 131 69 133 192 237 8 16 211 70 12 34 89 248 218 123 248 24 20 142 75 58 193 158 151 248 242 92 24 33 99 19 200 211 134 69 142 100 51 97 80 150 196 72 234 84 59 179 171 188 144 188 36 33 32 80 48 133 95 125 125 89 44 74 103 136 200 148 41 26 26 26 15 56 197 138 73 155 84 144 179 189 35 198 237 38 173 182 121 137 111 189 47 68 108 245 63 174 175 98 155]
:c`"=i@b152519%110*+}%N*N"
$ cjam gen.cjam > test.cjam
$ cjam test.cjam < british-english-huge.txt | sort -n > temp
$ head -1 temp
8
$ tail -1 temp
16776899
$ all=$(wc -l < british-english-huge.txt)
$ unique=$(uniq -u < temp | wc -l)
$ echo $[all - unique]
3677

The following port to Python can be used with the official scoring snippet:
h=lambda s,b:len(s)and ord(s[-1])+b*h(s[:-1],b)

def H(s):
 p=h(s,9)%110
 return h(s,ord(
  '}\x13%ww"\x0c\xe1\xf5{\x83E\x85\xc0\xed\x08\x10\xd3F\x0c"Y\xf8\xda{\xf8\x18\x14\x8eK:\xc1\x9e\x97\xf8\xf2\\\x18!c\x13\xc8\xd3\x86E\x8ed3aP\x96\xc4H\xeaT;\xb3\xab\xbc\x90\xbc$! P0\x85_}}Y,Jg\x88\xc8\x94)\x1a\x1a\x1a\x0f8\xc5\x8aI\x9bT\x90\xb3\xbd#\xc6\xed&\xad\xb6y\x89o\xbd/Dl\xf5?\xae\xafb\x9b'
  [p]))%152519*110+p

I've ported my code to Python for easy verification.

Does h in that Python port correspond to a CJam builtin?

Yes. It's CJam's b (base conversion).

Is your scoring process in bash?

@GamrCorps Yes, that's Bash.

Python, 6446 6372

This solution achieves lower collision count than all previous entries, and it needs only 44 of the 140 bytes allowed for code:
H=lambda s:int(s.encode('hex'),16)%16727401

@mbomb007 orlp's own submission does %(2**24-1), so I think it might be good to ask for clarification

@mbomb007 The challenge says no such thing. It says the function must take an ASCII string as input and output an integer in that range. Regardless of which input you give my function, the output will be in that range. The mathematical definition of the word function does not require it to produce every allowed output. If that's what you wanted the mathematical term you'd be using was surjective function. But the word surjective was not used in the requirements.

@mbomb007: There is no requirement that hash functions be surjective. For example, many memory-address-based hash functions can only produce multiples of some small power of 2 due to memory alignment, including the default object hash in older versions of Python. Many hash functions even have a smaller domain than codomain, so they couldn't be surjective anyway.

@mbomb007 - In fact, given there are far more number values from [0, 2**24-1] than there are words in the English language, it would be mathematically impossible to make a hash where every single value in that range was possible.

JavaScript (ES6), 6389
The hash function (105 bytes):
s=>[...s.replace(/[A-Z]/g,a=>(b=a.toLowerCase())+b+b)].reduce((a,b)=>(a<<3)*28-a^b.charCodeAt(),0)<<8>>>8

The scoring function (NodeJS) (170 bytes):
h={},c=0,l=require('fs').readFileSync(process.argv[2],'utf8').split('\n').map(a=>h[b=F(a)]=-~h[b])
for(w of Object.getOwnPropertyNames(h)){c+=h[w]>1&&h[w]}
console.log(c)

Call as node hash.js dictionary.txt, where hash.js is the script, dictionary.txt is the dictionary text file (without the final newline), and F is defined as the hashing function.
Thanks Neil for shaving 9 bytes off the hashing function!

Why the assignment to a? Also, instead of ((...)>>>0)%(1<<24) you can probably use (...)<<8>>>8.

@Neil Because alphabet, and I'm boring =P Also, nice bitwise mathing! That saved 7 bytes =)

Good thing this isn't code golf, otherwise I'd have to ding you for the unused variable i as well.

@Neil Crap >_< I use that while testing some alternative hashing ideas and forgot to remove XD Yes, good thing this isn't a golf, though all the same, I'd love it if I could compress the hash and scoring functions into the same 140 bytes, so every bit helps ;)

@Neil Same thing with my (a=...) deal (thought you meant why I used a ad my variable name haha). Removed that as well, and now down to 57.

@Sp3000 Gah, I see what you mean. Mine is not counting the ones that are in there initially when the collision is found. I'll fix that.

Ok, I'm going to stop rushing this and get an actual fix out here.

@Sp3000 How's this look?

I can't check the JS since I don't have node on this computer, but I've got the same score from porting to Python.

Let's take a crack at that scoring function... maybe if you use a=>h[b=F(a)]=-~h[b] and c+=h[w]>1&&h[w]?

By what appears to be pure coincidence, your latest edit got you the exact same score as the Mathematica answer.

@kasperd Indeed haha, I noticed that coincidence. I actually found a better one, but I'm spending a little more time searching before I update.

CJam, 6273
{49f^245b16777213%}

XOR each character with 49, reduce the resulting string via x, y ↦ 245x + y, and take the residue modulo 16,777,213 (the largest 24-bit prime).
Scoring
$ cat hash.cjam
qN% {49f^245b16777213%} %N*N
$ all=$(wc -l < british-english-huge.txt)
$ unique=$(cjam hash.cjam < british-english-huge.txt | sort | uniq -u | wc -l)
$ echo $[all - unique]
6273

I reimplemented the algorithm in python from your description. I can confirm that your score checks out with the official score computation.

Python, 340053
A terrible score from a terrible algorithm, this answer exists more to give a small Python script that displays scoring.
H=lambda s:sum(map(ord, s))%(2**24)

To score:
hashes = []
with open("british-english-huge.txt") as f:
    for line in f:
        word = line.rstrip("\n")
        hashes.append(H(word))

from collections import Counter
print(sum(v for k, v in Counter(hashes).items() if v > 1))

It could be useful to have the scoring code assert that the return value from the hash function is an integer in the permitted range.

Mathematica, 6473
The next step up... instead of summing the character codes we treat them as the digits of a base-151 number, before taking them modulo 224.
hash[word_] := Mod[FromDigits[ToCharacterCode @ word, 151], 2^24]

Here is a short script to determine the number of collisions:
Total[Last /@ DeleteCases[Tally[hash /@ words], {_, 1}]]

I've just tried all bases systematically from 1 onwards, and so far base 151 yielded the fewest collisions. I'll try a few more to bring down the score a bit further, but the testing is a bit slow.

Javascript (ES5), 6765
This is CRC24 shaved down to 140 Bytes.  Could golf more but wanted to get my answer in :)
function(s){c=0xb704ce;i=0;while(s[i]){c^=(s.charCodeAt(i++)&255)<<16;for(j=0;j++<8;){c<<=1;if(c&0x1000000)c^=0x1864cfb}}return c&0xffffff}

Validator in node.js:
var col = new Array(16777215);
var n = 0;

var crc24_140 =
function(s){c=0xb704ce;i=0;while(s[i]){c^=(s.charCodeAt(i++)&255)<<16;for(j=0;j++<8;){c<<=1;if(c&0x1000000)c^=0x1864cfb}}return c&0xffffff}

require('fs').readFileSync('./dict.txt','utf8').split('\n').map(function(s){
    var h = crc24_140(s);
    if (col[h]===1) {
        col[h]=2;
        n+=2;
    } else if (col[h]===2) {
        n++;
    } else {
        col[h]=1;
    }
});

console.log(n);

Welcome to Programming Puzzles & Code Golf!

...And thanks for the warm welcome @AlexA.!

Python, 6390 6376 6359
H=lambda s:reduce(lambda a,x:a*178+ord(x),s,0)%(2**24-48)

May be considered a trivial modification to Martin Büttner's answer.

@mbomb007 That's not true. If your function always outputs 4 it's still outputting in the range [0, 2**24-1]. The only thing that's not allowed is outputting any number not inside that range, e.g. -1 or 2**24.

Python, 9310

Yeah, not the best, but at least it is something. As we say in crypto, never write your own hash function.
This is exactly 140 bytes long, as well.
F=lambda x,o=ord,m=map:int((int(''.join(m(lambda z:str(o(z)^o(x[-x.find(z)])^o(x[o(z)%len(x)])),x)))^(sum(m(int,m(o,x))))^o(x[-1]))%(2**24))

Matlab, 30828 8620 6848
It builds the hash by assigning a prime number to each ascii character/position combo and calculating their product for each word modulo the largest prime smaller than 2^24.  Note that for testing I moved the call to primes outside into the tester directly before the while loop and passed it into the hash function, because it sped it up by about a factor of 1000, but this version works, and is self-contained.  It may crash with words longer than about 40 characters.
function h = H(s)
p = primes(1e6);
h = 1;
for i=1:length(s)
    h = mod(h*p(double(s(i))*i),16777213);
end
end

Tester:
clc
clear variables
close all

file = fopen('british-english-huge.txt');
hashes = containers.Map('KeyType','uint64','ValueType','uint64');

words = 0;
p = primes(1e6);
while ~feof(file)
    words = words + 1;
    word = fgetl(file);
    hash = H(word,p);
    if hashes.isKey(hash)
        hashes(hash) = hashes(hash) + 1;
    else
        hashes(hash) = 1;
    end
end

collisions = 0;
for key=keys(hashes)

    if hashes(key{1})>1
        collisions = collisions + hashes(key{1});
    end
end

If you want to save space in your program, you don't have to convert your char to a double explicitly. Also you could use numel rather than length. Not sure what you'd do with all those extra bytes though!

Java 8, 7054 6467
This is inspired by (but not copied from) the builtin java.lang.String.hashCode function, so feel free to disallow according to rule #2.
w -> { return w.chars().reduce(53, (acc, c) -> Math.abs(acc * 79 + c)) % 16777216; };

To score:
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.Function;

public class TweetableHash {
    public static void main(String[] args) throws Exception {
        List<String> words = Files.readAllLines(Paths.get("british-english-huge.txt"));

        Function<String, Integer> hashFunc = w -> { return w.chars().reduce(53, (acc, c) -> Math.abs(acc * 79 + c)) % 16777216; };

        Map<Integer, Integer> hashes = new HashMap<>();
        for (String word : words) {
            int hash = hashFunc.apply(word);
            if (hash < 0 || hash >= 16777216) {
                throw new Exception("hash too long for word: " + word + " hash: " + hash);
            }

            Integer numOccurences = hashes.get(hash);
            if (numOccurences == null) {
                numOccurences = 0;
            }
            numOccurences++;

            hashes.put(hash, numOccurences);
        }

        int numCollisions = hashes.values().stream().filter(i -> i > 1).reduce(Integer::sum).get();
        System.out.println("num collisions: " + numCollisions);
    }
}

@muddyfish could you check out the current version? i think ive accounted for 3-way-collisions and am still getting the same result.

This doesn't account for three-way collisions. If you replace hashes with Map<Integer, Integer> hashes = new HashMap<>() and then count the number of words for each hash, you can account for them correctly.

Your scoring still looks incorrect. I think to compute a correct score, you have to output numHashes + numCollisions. (Which I guess will put you close to my 6832 estimate for a random oracle.)

Modify the grading portions to this: http://pastebin.com/nLeg4qut

yeah, fixed the grading and it looks like a much more reasonable value now, ty

C#, 6251 6335
int H(String s){int h = 733;foreach (char c in s){h = (h * 533 + c);}return h & 0xFFFFFF;}

The constants 533 and 733 889 and 155 give the best score out of all of the ones I've searched so far.

Ruby, 9309 collisions, 107 bytes
def hash(s);require'prime';p=Prime.first(70);(0...s.size).reduce(0){|a,i|a+=p[i]**(s[i].ord)}%(2**24-1);end

Not a good contender, but I wanted to explore a different idea from other entries.
Assign the first n primes to the first n positions of the string, then sum all prime[i] ** (ascii code of string[i]), then mod 2**24-1.

Python, 6995 6862 6732
Just a simple RSA function. Pretty lame, but beats some answers.
M=0x5437b3a3b1
P=0x65204c34d
def H(s):
    n=0
    for i in range(len(s)):
        n+=pow(ord(s[i]),P,M)<<i
    return n%(8**8)

C++: 7112 6694 6483 6479 6412 6339 collisions, 90 bytes
I implemented a naïve genetic algorithm for my coefficient array. I'll update this code as it finds better ones. :)
int h(const char*s){uint32_t t=0,p=0;while(*s)t="cJ~Z]q"[p++%6]*t+*s++;return t%16777213;}

Test function:
int main(void)
{
    std::map<int, int> shared;

    std::string s;
    while (std::cin >> s) {
        shared[h(s.c_str())]++;
    }

    int count = 0;
    for (auto c : shared) {
        if ((c.first & 0xFFFFFF) != c.first) { std::cerr << "invalid hash: " << c.first << std::endl; }
        if (c.second > 1) { count += c.second; }
    }

    std::cout << count << std::endl;
    return 0;
}

tcl
88 bytes, 6448 / 3233 collisions
I see people have been counting either the number of colliding words,
or else the number of words placed in nonempty buckets. I give both counts - the first is according to the problem specification, and the
second is what more posters have been reporting.
# 88 bytes, 6448 collisions, 3233 words in nonempty buckets

puts "[string length {proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}}] bytes"

proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}

# change 2551 above to:
#   7: 85 bytes, 25839 colliding words, 13876 words in nonempty buckets
#   97: 86 bytes, 6541 colliding words, 3283 words in nonempty buckets
#   829: 87 bytes, 6471 colliding words, 3251 words in nonempty buckets

# validation program

set f [open ~/Downloads/british-english-huge.txt r]
set words [split [read $f] \n]
close $f

set have {};                        # dictionary whose keys are hash codes seen
foreach w $words {
    if {$w eq {}} continue
    set h [H $w]
    dict incr have $h
}
set coll 0
dict for {- count} $have {
    if {$count > 1} {
        incr coll $count
    }
}
puts "found $coll collisions"

Where do you see answers using the incorrect method for computing the score? There has been a lot, but they were all corrected or deleted years ago. I see four answers remaining with scores less than 6000 because those four answers have actually been optimized to have such low scores.

As far as I can tell, your code is proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}...right?

@EriktheOutgolfer: Yes, it is

I second @kasperd: Can you point what answers are not accounting the collisions according to question spec? Did you really tried to run them?

JavaScript, 121 bytes, 3268 3250 3244 6354(3185) collisions
s=>{v=i=0;[...s].map(z=>{v=((((v*13)+(s.length-i)*7809064+i*380886)/2)^(z.charCodeAt(0)*266324))&16777215;i++});return v}

Parameters (13, 7809064, 380886, 2, 266324) are by trial and error.
Still optimizable I think, and there is still room for adding extra parameters,
working for further optimization...
Verification
hashlist = [];
conflictlist = [];
for (x = 0; x < britain.length; x++) {
    hash = h(britain[x]);                      //britain is the 340725-entry array
    hashlist.push(hash);
}

conflict = 0; now_result = -1;
(sortedlist = sort(hashlist)).map(v => {
    if (v == now_result) {
        conflict++;
        conflictlist.push(v);
    }
    else
        now_result = v;
});

console.log(conflictlist);

var k = 0;
while (k < conflictlist.length) {
    if (k < conflictlist.length - 1 && conflictlist[k] == conflictlist[k+1])
        conflictlist.splice(k,1);
    else
        k++;
}

console.log(conflict + " " + (conflict+conflictlist.length));

3268 > 3250 - Changed the 3rd parameter from 380713 to 380560.
3250 > 3244 - Changed the 3rd parameter from 380560 to 380886.
3244 > 6354 - Changed the 2nd parameter from 7809143 to 7809064, and found I've used the wrong calculation method ;P

Python 3, 89 bytes, 6534 hash collisions
def H(x):
 v=846811
 for y in x:
  v=(972023*v+330032^ord(y))%2**24
 return v%2**24

All the large magic numbers you see here are fudge constants.

Here are a few similar constructs, which are quite "seedable" and makes incremental parameter optimization possible. Damn it is difficult to get lower than 6k! Assuming the score has the mean of 6829 and std of 118 I also calculated the likelihood of getting such low scores by random.
Clojure A, 6019, Pr = 1:299.5e9
 #(reduce(fn[r i](mod(+(* r 811)i)16777213))(map *(cycle(map int"~:XrBaXYOt3'tH-x^W?-5r:c+l*#*-dtR7WYxr(CZ,R6J7=~vk"))(map int %)))

Clojure B, 6021, Pr = 1:266.0e9
#(reduce(fn[r i](mod(+(* r 263)i)16777213))(map *(cycle(map int"i@%(J|IXt3&R5K'XOoa+Qk})w<!w[|3MJyZ!=HGzowQlN"))(map int %)(rest(range))))

Clojure C, 6148, Pr = 1:254.0e6
#(reduce(fn[r i](mod(+(* r 23)i)16777213))(map *(cycle(map int"ZtabAR%H|-KrykQn{]u9f:F}v#OI^so3$x54z2&gwX<S~"))(for[c %](bit-xor(int c)3))))

Clojure, 6431, Pr = 1:2.69e3 (something different)
#(mod(reduce bit-xor(map(fn[i[a b c]](bit-shift-left(* a b)(mod(+ i b c)19)))(range)(partition 3 1(map int(str"w"%"m")))))16776869)

This was my original ad-hoc hash function, it has four tunable parameters.

The trick to a low score is a string constant in which each character can be optimized independently without ruining the optimization you have done for the other characters.

Yeah, I tried optimizing for only shorter strings first, as appending more characters to the "entropy" string doesn't affect those (once the multiplier of r is fixed). But still my search algorithm is essentially brute force, and I'm not sure if the initial choice of the multiplier of r is important or not.

Maybe just multiplying ASCII values does not bring enough entropy to the game. Many well-scoring algorithms seem to have the form f(n) % (8^8 - g(n)).

There is one answer which explains how it got as low as 3677. The ones scoring even lower than that have little explanation.

tcl
#91 bytes, 6508 collisions
91 bytes, 6502 collisions
proc H s {lmap c [split $s ""] {incr h [expr [scan $c %c]*875**[incr i]]};expr $h&0xFFFFFF}

Computer is still performing a search to evaluate if there is a value that causes less collisions than the 147 875 base, which is still the recordist.

Ruby, 6473 collisions, 129 bytes
h=->(w){@p=@p||(2..999).select{|i|(2..i**0.5).select{|j|i%j==0}==[]};c=w.chars.reduce(1){|a,s|(a*@p[s.ord%92]+179)%((1<<24)-3)}}

The @p variable is filled with all the primes below 999.
This converts ascii values into primes numbers and takes their product modulo a large prime. The fudge factor of 179 deals with the fact that the original algorithm was for use in finding anagrams, where all words that are rearrangements of the same letters get the same hash. By adding the factor in the loop, it makes anagrams have distinct codes.
I could remove the **0.5 (sqrt test for prime) at the expense of poorer performance to shorten the code. I could even make the prime number finder execute in the loop to remove nine more characters, leaving 115 bytes.
To test, the following tries to find the best value for the fudge factor in the range 1 to 300. It assume that the word file in in the /tmp directory:
h=->(w,y){
  @p=@p||(2..999).
    select{|i|(2..i**0.5).
    select{|j|i%j==0}==[]};
  c=w.chars.reduce(1){|a,s|(a*@p[s.ord%92]+y)%((1<<24)-3)}
}

american_dictionary = "/usr/share/dict/words"
british_dictionary = "/tmp/british-english-huge.txt"
words = (IO.readlines british_dictionary).map{|word| word.chomp}.uniq
wordcount = words.size

fewest_collisions = 9999
(1..300).each do |y|
  whash = Hash.new(0)
  words.each do |w|
    code=h.call(w,y)
    whash[code] += 1
  end
  hashcount = whash.size
  collisions = whash.values.select{|count| count > 1}.inject(:+)
  if (collisions < fewest_collisions)
    puts "y = #{y}. #{collisions} Collisions. #{wordcount} Unique words. #{hashcount} Unique hash values"
    fewest_collisions = collisions
  end
end

The score looks suspicious. Are you sure you are counting all the colliding words? Several previous answers mistakenly counted only one word for each colliding hash value.

You may be right. I must consider how I counted and see if it is the same as your definition. I am counting how many words there are and subtracting how many unique hashcodes were generated. If words A and B get the same hashcode, is that one collision or two? I count it as one.

I didn't define the scoring function. I just copied it from the example answer posted by the same user who posted the challenge. Most answers have scores ranging between 6273 and 6848. There have been multiple answers each making the same mistake in the score computation leading to computing a score approximately half of what it should have been. (Exactly half the correct score if there are no cases of three colliding words.)

Yes, I made the same mistake. I will amend my answer later. Got to catch a bus.

Fixed the scoring.

Why @p and now just p?


text:
Shortest code for infinite disk I/O
(Just open 50 tabs in Google Chrome :D (just kidding, no you can't))
Shortest code for infinite disk I/O any language, C# example:
using System.IO;

namespace FileApp {
    static class Program {
        public static void Main() {
            do {
                File.WriteAllText("a", "a");
                File.Delete("a");
            } while (true);
        }
    }
}

You can't just fill the entire disk though, as then it would halt in the end and would be finite.
And you can't do reading only, infinite writing has to happen. (It has to kill my SSD after enough runtime.)
Get cracking! :)

Does reading files instead of writing them also count as disk I/O? What about writing to /dev/null? (Is yes>/dev/null a valid Bash answer?)

Good point, I changed the question to require infinite writing.

Can it take any input ?

Sure, as long as it is not infinite user input.

This is heavily biased towards shell scripts, but such is life.

Dang man...what did your SSD do to you?

Would this kill the ssd though? Wouldn't the writes get cached (kernel or disk cache) and then removed again before hitting the nand chips?

As I can't hope to compete with 6 byte solutions, would creating the file ./a with the 3 byte contents ./a count for a bonus prize for lateral thinking? AFAIK just executing a file causes some file system writing to take place on many systems, because at the very least 'last access time' gets updated as a byproduct ;-)

Can't stay. Giving talk. Oh no, they switched to my screen...where is it...ah, there! Bye!

(Note: I actually showed that during the talk a couple of minutes ago.)

Many of these answers will write the data into the same space over and over.  That does not result in an actual disk write even if the data differs.  (Extreme case, dos -> windows communications.  I wrote 4k of data in dos and read it back in Windows--so long as data was flowing the disk light would stay off.)

Does "infinite" here mean "until an error occurs" (e.g. disk full), or literally infinite?  If you write sequentially until the disk is full, are you allowed to quit, or do you have to start over?

Literally infinite, the disk cannot be full.

@Doorknob /dev/null is provided by Linux/Mac/whatever kernel, it isn't on the disk (or at least will not affect the disk when written to).

um...what? Infinite disk I/O is a sure way of sentencing your SSD to death.

I was referring to CatsAreFluffy ;)

@Stilez: A program that just exec's itself repeatedly, to create access-time metadata I/O on file holding the script?  That will work as well as most answers on systems that don't use the default lazy relatime or noatime mount options.  However, 3 bytes won't do it: you'll run out of PIDs.  (Some of the script answers have the same problem.  Programs with resource leaks aren't going to be able to wear out an SSD before crashing).

Does it need to be disk I/O, or will tape I/O work?

DOS/Batch: 4 bytes
%0>x

This batch file will call itself (%0) and redirect (>) the output to a file called x. Since echo is on by default, this will output the path and command.

Will this run out of disk space eventually, or is the output overwritten?

@MathuSumMut: With > it will be overwritten. >> would append

You win then I guess :P

Why can't echo be off before running this? (I've seen many answers like this)

@ΈρικΚωνσταντόπουλος: if echo is off, only explicit output is shown on the console. Things like commands and even the prompt will disappear. %0 is the only thing that could generate output, but it doesn't do that on its own, it needs the shell to output a copy of the command implicitly.

@ThomasWeller I mean someone might have turned off echo before running this code.

@ΈρικΚωνσταντόπουλος: That's true. In that case, a file with 0 byte is produced, not generating I/O as expected by this challenge. But it's not our task to consider every case, otherwise you might want to turn off caching, virus scanners, ...

Writing a 0 byte file will still cause disk I/O, as it has to update the last-modified time within the directory.

PowerShell v2+, 10 bytes
for(){1>1}

Simply loops infinitely with an empty for loop. Each iteration, we output the integer 1 (implicitly converted to a string) with the > redirect operator, which overwrites the file named 1 in the local directory.

Could you replace the second 1 with anything else (that makes a valid file name) or does it have to be 1?

On my Windows VM, Winload.exe is sufficient...

I think it has to be a number because if it is a letter then it would be treated as a variable, to treat it as a string quotes are required, and they waste bytes. :P

@QPaysTaxes MathuSum has it correct. The second 1 needs to be a number of some sort in order for the implicit parsing to work correctly. Anything from [0-9] would work the same.

Love seeing a PowerShell answer score so high! However I don't understand your statements about the second 1 needing to be a number - it seems to work fine for me with a instead, and i dont see why powershell would parse it as anything other than the string a

@Nacht Maybe it's a quirk of my particular environment, then. In my ISE (PSv4 Win8.1), replacing the second 1 with anything non-numeric (and not specified either as .\a or a.txt or the like) results in a parse error.

@Nacht OK, now I'm definitely convinced it's a bug in my particular environment, since for(;;){1>a} works fine.

Pyth, 6 bytes
#.w]]0

Pyth's only file output command is .w. When called on a string, it writes that string to a file in append mode, which is no good for the purpose of this question. When called on a 2-d array, it writes the corresponding image to that file, overwriting the file contents. That's what this program does. The default file output name is o.png, so this program infinitely overwrites the file o.png with a 1-pixel white image. # is an infinite loop.

If you want a shorter (but more boring than my other one) answer:
Bash, 5 bytes
>w;$0

I could make that shorter if there's a command (less than 3 bytes long) that writes something to disk I/O.  Something like sync would work, but sync is 4 bytes
Note: this doesn't work when run straight from bash, only when put in a script and run as the script name. (i.e. echo 'w>w;$0' > bomb; chmod 755 bomb; ./bomb)

Looks like it's a tie between me and @isaacg - who wins?

I prefer using exec (or . $0). I think this will run out of PIDs.

Is the first w needed here? For me simply >w creates an empty file w, and doing that in a loop will create infinite I/O because the mtime metadata needs to be updated continually.

If that qualifies @HenningMakholm then I'll put it in.

hmm...I think it qualifies as good rule circumventing, although the winner was already announced, but you can still post it if you like. :)

@MathuSumMut I made an edit.  Personally I feel that mine should be counted simply as the bash code itself for the bytecount.  Every other entry here must be executed as a script in a file, so how is mine different?

Alright bro, enjoy

If it only works if put into a script, than the script should also be taken into consideration when calculating the size. Just when I access external resources, it also adds to the code size.

The script only contains these bytes.  Since it's bash there's no compiler or anything fancy needed.

Ruby, 22 20 bytes
loop{open(?a,?w)<<1}

Repeatedly truncates and writes a 1 to the file a.
Thanks to Ventero for 2 bytes!

open(?a,?w)<<1 to save 2 bytes.

Thank you, doorknob, for honouring us with your presence. I am humbled.

Does that leak file descriptors?  Or does it get closed when it goes out of scope?  (IDK Ruby, sorry).

cmd, 14 bytes
:a
cd>1
goto a

Infinitly overwrites the file 1 with the string to the current directory

I'm new here:
Are windows new lines (CR LF) counted as two bytes?

Welcome to PPCG! Windows, at least modern systems, should be able to handle just LF without issue. The above works for me with just LF on Windows 8.1, so your 14 bytes is correct.

CR LF2CR1LF1

Bash + coreutils, 10
yes \>b|sh

Writes a continuous stream of >b, which is piped to sh for evaluation.  >b simply truncates a file called b to zero bytes each time.

+1 because your name is really appropriate to what this snippet of code will do

Why b and not c?

Perl 5, 27 32 22 bytes
{{open my$h,'>o'}redo}

If simply changing the modification timestamp of a file suffices...
Quick explanation:
{ # Braces implicitly create/mark a loop.
    { # They also create closures, for `my` variables.
        open my $filehandle, '>', 'o';    # Writing to file "o".
        # close $filehandle;   # Called implicitly when
                               # variable gets destroyed.
    } # $filehandle gets destroyed because there are no references to it.
    redo; # ...the loop.
}

Previous solution (32 bytes): {{open my$h,'>o';print$h 1}redo}
Edit: {open F,'O';print F 1;redo} ← Didn't test the code before posting; now I had to correct it.

:o a perl variable not prefixed with $!

@cat: It's not a regular variable, like a scalar, array, or hash. It is simply a bareword. Depending on context, a bareword can be taken as a sub (a function), a glob, I think, or a filehandle. (Maybe others too?)

PHP, 60 30 17 16 15 bytes
Updated yet again as per @manatwork suggested:
while(!`cd>1`);

Also now tested.

A bit of cheating 22 bytes:
while(exec('>1 dir'));
Earlier suggestion by @manatwork 30 bytes:
while(file_put_contents(1,1));
NOT TESTED (no php available on this computer) 43 bytes:
for($a=fopen(1,'w');fputs($a,1);fclose($a))
A golfed original 45 bytes:
$a=fopen(1,'w');while(fputs($a,1))rewind($a);
My first post here, joined because I just had to try this out: as long as file write succeeds, rewind file pointer to start.

Just can't get smaller than the file_put_contents().

while(file_put_contents(1,1)); should be enough. Note that running full scripts from command line as php -r '…' is acceptable as per consensus on meta Running PHP with -r instead of code tags.

Is this actually writing to disk or just a buffer in memory?

@manatwork Oh man! I knew there's always room for improvement, but that much... too bad that function hasn't got shorter name. :D I don't know about the buffer.. I wonder if I should update the answer with that shorter solution.

If it's shorter, please do update your answer, go ahead! :)

Is it allowed to call exec() from php? I realize it is no more in php's "scope".

Yes, executing external commands is allowed by default. Sadly your while(exec('>1 dir')); idea will not work as is: exec()'s return value is the last line from the executed command's stdout. As you are redirecting the execute command's output to a file, nothing will reach stdout, so exec() will return empty string. Which being falsy value in PHP, the while will immediately terminate. Fortunately negating the condition is quite short. By the way, better use the Execution Operators instead of exec(): while(!\>1 dir`);`.

That's just wrong, having such shorthands in php.. nice solution though.

C, 95 94 93 89 78 90 89 76 75 bytes
#include<stdio.h>
main(){for(FILE*f=fopen("a","w");;fputc(0,f),fclose(f));}

Again, sudo watch -n1 lsof -p `pidof inf`  seems to say this is valid.
HOW DID I NOT SEE THAT SPACE D:<
Thanks @Jens for shaving off 13 bytes :D

The w+ mode is read and write, initially truncating the file. Since you don't need to read, you can shave off a byte with just w, which also truncates the file, but doesn't open the file in read mode.

No need for return 0; if the loop never terminates.

Why not use fputc(1,f) instead of the super-verbose fprintf(f," ")?

main(){for(FILE*f=fopen("a","w");;fputc(1,f),fclose(f));} since an empty conditional in for means true. 76 bytes.

@Jens because of course I didn't know about fputc. Now I do :D

You don't need the fputc at all.  fopen/fclose will cause disk I/O for the metadata.  Also, you appear to have two ;; back to back.  Also, @Jens: you never need return 0 in main: the C standard specifies an implicit return 0 at the end of main.  Even if not, you'd just return whatever happened to be left in the return-value register, which is fine.  Outside of golfing, you should of course return 0 explicitly at the end of main, and use its proper function signature!

Also, you don't need sudo for lsof to work on your own processes.

@PeterCordes The two ;; are in for(;;) and on purpose as explained. They are required.

@Jens: oh, I didn't notice that was inside the for() condition, rather than the body.  That means the fopen() only happens once, so all but the first iteration is operating on a closed FILE*.  It crashes on Linux (double-free detected on the fclose of the already-closed FILE*), and there's no way it can possibly do what we need on any system, because we need fopen to run repeatedly to truncate.

@Jens: here's a working version that's the same length, taking advantage of the required ;s in the for structure: main(){for(FILE*f;f=fopen("a","w");fclose(f))fputc(0,f);}.  I actually tested it, and it runs, actually producing disk activity on Linux.  (Also see my C and C++ answers, though.)

I incorporated that into my own answer, with improvements.  (e.g. don't include stdio.h)

I left an edit which fixed the bug and added an ungolfed version, but reviewers rejected it with a claim that it "deviates from the original intent".  I thought it might be rejected, but not with that reason.  Oh well, I give up on trying to save time for future readers seeing this version.

@PeterCordes PPCG is not Stack Overflow; please do not make edits to others' answers which change code or other major parts of the answer. Typo fixes are fine, but anything beyod that (including corrections of factually incorrect statements) should be suggested in the comments.

Thanks for the clue on etiquette on this site.  I had hoped that adding explanations / ungolfed versions would be appreciated :/.  Any idea how that reject reason makes sense, though?  Obviously the "original intent" wasn't to be wrong.  Or is this a common thing on PPCG, where none of the canned responses are "too big a change", so you just use that?  I expected that if it was rejected, it would be for "too big", or "self promotion".

@PeterCordes Well, on most SE sites, collaboration and editing is welcomed but on PPCG, which is unique, a users' answer is sorta sacred and by changing their code or making other large changes, you do "deviate from the original intent of the author" (whereas this is typically fine on SO, etc). Also, the "canned-response-is-wrong-or-slightly-off" phenomena is in fact SE-wide, and Mother Meta gets many many posts about it. :)

@PeterCordes If you have any questions about this or PPCG in general, you can always come say hi in chat or post on meta.

Let us continue this discussion in chat.

sh, 11 bytes
w>w;exec $0

Save this to a file without special characters, such as loop.sh, make it executable, and run it with ./loop.sh or similar.
This writes the output of the command w to the file w, overwriting the previous value each time. Then, it replaces itself with a fresh version of the same program, so it can run infinitely.

this is missing a second >. also, assuming you have a "special" $PATH and "special" umask/filesystem, you can go for w>>w;$0, brining it down to 7 chars

@mnagel >> is append, it will eventually fill the disk

@mnagel but you're right about not needing exec,I didn't realize that. Someone else has done it, so I won't update, though

Or . $0 instead of exec $0, perhaps? I don't know if that will run cause a stack overflow or something, though. ... Yep, it segfaulted.

CPython 3.5, 33 16 bytes
while 1:open("a")

Yes, really. :D

while 1:open("a","w") is shorter and strace shows that python is doing open, fstat64 and close, definitely I/O operations. If the file a already exists, it can be even shorter: while 1:open('a') which still generates an open, fstat64 and close, and even modifies atime of the file.

@RadovanGarabík :0 Thank you, I didn't know that handy piece of information! Of course, it's implementation specific.

Bash, 26 bytes
yes>y&while :;do rm y;done

If I were to expand this one-liner, I would get this:
yes > y &      # Write out infinitely to the file y in the current directory
while true     # Let's do something forever
do             # Here's what we're going to do
    rm y       # delete y
done           # That's all we're going to do

This can't exactly compete with the 10 byte PowerShell line, but it'll hold its own against the others.  See my other answer for the 6 byte version.

while :;ls>l;done

The good old exec trick will do better: ls>l;exec $0. Shorter, but boring.

:>l;exec $0 - file creation is writing the inode

Also if you don't have the 'l' alias, you could use 'w'

@manatwork That will run out of disk space, will it not?

@Daniel No, > overwrites.

Ah, my bad *facepalm*

Even though you delete y, yes will still continue to write to the same file handle that it had. Run lsof | grep yes and you should see something like /path/to/y (deleted).  This will fill up the disk and fail.

Instead of rm y you can use >y which will truncate the existing file. It is also a bit shorter.

TI-BASIC, 12 bytes
While 1
Archive A
UnArchive A
End

Alternate solution by user lirtosiast with the same size:
While 1
SetUpEditor
Archive ∟1
End

This will work on the TI-83+ and TI-84+ series of calculators.
Yes, this also works if A is already archived or is not initialized at all at the start of the program! The program is only 12 bytes because of tokenization.

I don't know if the flash memory used by the calculators counts as "disk".

@lirtosiast In Jamy's defense, SSDs are made of flash memory =)

In any case, the byte count is at least 10 bytes less. The 2nd Mem screen counts a header equal to 9 bytes + the length of the program name, but we don't here so you can subtract it out.

@lirtosiast This repeatedly writes and reads to the ROM (permanent memory) of the calculator, not the RAM. Of course, calculators don't have an actual hard drive inside :)

@lirtosiast Thanks, I didn't know about that! (I was wondering why the amount of bytes my TI-84+ reported didn't match up with my hand-counting...) I've updated my answer.

I couldn't find anything shorter, but SetUpEditor:Archive L1 is the same size.

@lirtosiast Added your solution to my answer!

MATL, 10 bytes
`1[]T3$Z#T

Explanation
This is an infinite loop that writes number 1  to a file called inout in current directory, overwriting previous file's contents.
`       % do...while loop
  1     %   push number 1
  []    %   push empty array
  T     %   push "true"
  3$Z#  %   fwrite function. First input is file content. Second is file name;
        %   defaults to "inout" if empty. Third indicates that any previous
        %   file contents should be discarded
  T     %   push "true": loop condition
        % implicitly end loop. Loop condition is "true", so the loop is infinite

Haskell, 20 bytes
f=writeFile"b""a">>f

Write the string "a" to a file named "b" and repeat. writeFile overwrites the file if it exists.

ZSH, 14 bytes
for ((;;)) :>:

Zsh, unlike Bash and other Bourne-like shells, allows loops without the do ... done fence, provided the condition is suitably delimited.
Alternatively, with while:
while {} {:>:}

Note that : is a builtin. You can't suspend this loop.
The principle is the same as in Digital Trauma's answer - nothing is written to the file, the IO is purely from creating and truncating the file.

I gotta say, I never thought I'd see muru, the muru, come play Code Golf. Welcome to PPCG :D

@cat Thanks. :D I have played once before.

JavaScript (Node.js), 43 41 bytes
(c=x=>require("fs").writeFile("a",x,c))()

Writes null to a file named a, then repeat.

What about writing c or x to the file? Saves 2 bytes. Also, doesn't require\fs`` work?

@Charlie Good point with writing c or x. require\fs`unfortunately doesn't work, because using backticks to call a function calls it with the first arguments as["fs"](array, which first and only element is the passed string) instead of"fs"(just the string). Tryconsole.log`test`` for example.

Rust, 84 Bytes
fn main(){loop{use std::io::Write;std::fs::File::create("a").unwrap().write(b"a");}}

File::create truncates an existing file, thus ensuring that we don't run out of disk space.
The used Compiler (1.9 Nightly) issues a warning about the unused result of write(...) but compiles nevertheless.

C, 92 bytes
#include <stdio.h>
main(){for(FILE*f=fopen("a","w+");fprintf(f," "),!fclose(f);;);return 0;}

While it looks like you could save 1 byte by
  for(FILE*f=fopen("a","w+");fprintf(f," ")+fclose(f);;){}

the problem with that loop is that + doesn't give you the guaranteed order.
Or recursive - shouldn't overflow if the compiler properly implements tail recursion (f is in an explicit inner scope)
85 bytes
#include <stdio.h>
main(){{FILE*f=fopen("a","w+");fprintf(f," ");fclose(f);}main();}

Hopefully the 85-byte version does not blow the stack. :P

@MathuSumMut: Easy fix: require compiling with optimizations. Tail call recursion saves the day.

There's a lot of scope for saving bytes here.  See my answer for packing stuff inside the for(;;), and for shorter functions than fprintf.  If you did need to include stdio.h (which you don't), you don't need a space: #include<stdio.h>

Mathematica, 14 bytes
For[,1>0,a>>a]

Repeatedly writes the string "a" to a file named a in the current directory, creating it if it doesn't exist.

would it write the string "a" or the contents of the variable a? And if the latter, what would it do if that variable were not yet defined?

@MichaelStern It writes the variable a, which is undefined, so it just writes a\n.

C, 40 bytes
main(){for(;;)write(open("a",1)," ",1);}

It will quickly run out of file descriptors, though; this can be overcome with:
45, 43 bytes
main(f){for(f=open("a",1);;)write(f,"",1);}

Why doesn't f have a type in the second?

@cat In C (very K&R style) it defaults to int.

gcc and clang won't compile the 2nd version.  Even GNU C doesn't allow dynamic initialization of a static/global variable (a call to open() isn't a compile-time constant).  Also, it will run out of disk space, because there's no lseek.  Maybe try utime("a","") in the loop, which will keep updating the ctime.  (You still have to open to create a file of known name).

@PeterCordes You're right, thanks for pointing out. Fixed.

Still doesn't satisfy the OP's requirement of not filling up the disk eventually, but maybe still worth keeping as an answer.  (Unless you have an idea better than my answer's close/reopen(O_TRUNC) in a loop.)  Contrary to my previous comment, updating timestamps only usually doesn't really produce actual disk I/O on Linux.  Like maybe one write per 24 hours with lazytime, as I said in my answer.

You can save two bytes in this fill-the-disk version:  put the f=open() in the run-once first statement of the for loop (saving a ;).  (I got that trick from cat's answer).  And, the empty string still has a 0-terminator, so you can take out the space in the string you pass to write(f,"",1).  Again, see my answer.)

@PeterCordes No, you're supposed to create an infinite I/O: appending to a file would not because it'd eventually stop due to OS failure (OP's specifically said that). You indeed see in the other answers it's just overwriting, in the accepted one foremost.

Ok, well this answer fails the requirement of running forever, since you keep appending one byte at a time with each write.  See my answer for code that doesn't.

@PeterCordes Why? 1 = O_WRONLY, which doesn't seek to the end (you'd also need O_APPEND).

write() advances the current file position by the number of bytes written.  Leaving off O_APPEND doesn't change that, it just changes the initial position of the file descriptor.  You could use pwrite(3,"",1,0) to keep over-writing byte 0 of the file, but that doesn't produce real disk activity on my Linux system.  Even close/reopen without O_TRUNC didn't light up my hard-drive LED.

mixing standards lol

C on amd64 Linux, 36 bytes (timestamp only), 52 49 bytes (real disk activity)
I hard-code the open(2) flags, so this is not portable to other ABIs.  Linux on other platforms likely uses the same O_TRUNC, etc., but other POSIX OSes may not.
+4 bytes to pass a correct permission arg to make sure the file is created with owner write access, see below.  (This happens to work with gcc 5.2)
somewhat-portable ANSI C, 38/51 bytes (timestamp only), 52/67 bytes (real disk activity)
Based on @Cat's answer, with a tip from @Jens.
The first number is for implementations where an int can hold FILE *fopen()'s return value, second number if we can't do that.  On Linux, heap addresses happen to be in the low 32 bits of address space, so it works even without -m32 or -mx32.  (Declaring void*fopen(); is shorter than #include <stdio.h>)

Timestamp metadata I/O only:
main(){for(;;)close(open("a",577));}   // Linux x86-64

//void*fopen();       // compile with -m32 or -mx32 or whatever, so an int holds a pointer.
main(){for(;;)fclose(fopen("a","w"));}

Writing a byte, actually hitting the disk on Linux 4.2.0 + XFS + lazytime:
main(){for(;write(open("a",577),"",1);close(3));}

write is the for-loop condition, which is fine since it always returns 1.  close is the increment.
// semi-portable: storing a FILE* in an int.  Works on many systems
main(f){for(;f=fopen("a","w");fclose(f))fputc(0,f);}                 // 52 bytes

// Should be highly portable, except to systems that require prototypes for all functions.
void*f,*fopen();main(){for(;f=fopen("a","w");fclose(f))fputc(0,f);}   // 67 bytes

Explanation of the non-portable version:
The file is created with random garbage permissions.  With gcc 5.2, with -O0 or -O3, it happens to include owner write permission, but this is not guaranteed.  0666 is decimal 438.  A 3rd arg to open would take another 4 bytes.  We're already hard-coding O_TRUNC and so on, but this could break with a different compiler or libc on the same ABI.
We can't omit the 2nd arg to open, because the garbage value happens to include O_EXCL, and O_TRUNC|O_APPEND, so open fails with EINVAL.

We don't need to save the return value from open().  We assume it's 3, because it always will be.  Even if we start with fd 3 open, it will be closed after the first iteration.  Worst-case, open keeps opening new fds until 3 is the last available file descriptor.  So, up to the first 65531 write() calls could fail with EBADF, but will then work normally with every open creating fd = 3.
577 = 0x241 = O_WRONLY|O_CREAT|O_TRUNC on x86-64 Linux.  Without O_TRUNC, the inode mod time and change time aren't updated, so a shorter arg isn't possible.  O_TRUNC is still essential for the version that calls write to produce actual disk activity, not rewrite in place.
I see some answers that open("a",1).  O_CREAT is required if a doesn't already exist.  O_CREAT is defined as octal 0100 (64, 0x40) on Linux.

No resource leaks, so it can run forever.  strace output:
open("a", O_WRONLY|O_CREAT|O_TRUNC, 03777762713526650) = 3
close(3)                                = 0
... repeating

or
open("a", O_WRONLY|O_CREAT|O_TRUNC, 01) = 3
write(3, "\0", 1)                       = 1   # This is the terminating 0 byte in the empty string we pass to write(2)
close(3)                                = 0

I got the decimal value of the open flags for this ABI using strace -eraw=open on my C++ version.
On a filesystem with the Linux lazytime mount option enabled, a change that only affects inode timestamps will only cause one write per 24 hours.  With that mount option disabled, timestamp updating might be a viable way to wear out your SSD.  (However, several other answers only do metadata I/O).

alternatives:
shorter non-working:
main(){for(;;)close(write(open("a",577),"",3));} uses write's return value to pass a 3 arg to close.  It saves another byte, but doesn't work with gcc -O0 or -O3 on amd64.  The garbage in the 3rd arg to open is different, and doesn't include write permission.  a gets created the first time, but future iterations all fail with -EACCESS.
longer, working, with different system calls:
main(c){for(open("a",65);pwrite(3,"",1);)sync();}  rewrites a byte in-place and calls sync() to sync all filesystems system-wide.  This keeps the drive light lit up.
We don't care which byte, so we don't pass 4th arg to pwrite.  Yay for sparse files:
$ ll -s a
300K -rwx-wx--- 1 peter peter 128T May 15 11:43 a

Writing one byte at an offset of ~128TiB led to xfs using 300kiB of space to hold the extent map, I guess.  Don't try this on OS X with HFS+: IIRC, HFS+ doesn't support sparse files, so it will fill the disk.
XFS is a proper 64bit filesystem, supporting individual files up to 8 exabytes.  i.e. 2^63-1, the maximum value off_t can hold.
strace output:
open("a", O_WRONLY|O_CREAT, 03777711166007270) = 3
pwrite(3, "\0", 1, 139989929353760)     = 1
sync()                                  = 0
pwrite(3, "\0", 1, 139989929380071)     = 1
sync()                                  = 0
...

Racket, 46 bytes
(do()(#f)(write-to-file'a"f"#:exists'replace))

I was thinking of answering in Racket, but you beat me to it. :P

Out of curiosity, did you find a shorter answer?

CBM BASIC 7.0, 9 bytes
0dS"a":rU

This program, when run, repeatedly saves itself to disk.  Here's a more readable version which doesn't use BASIC keyword abbreviations:
0 dsave "a" : run

Does it run out of cassette tape though? ;)

@MathuSumMut that would be 0 SAVE "A" : RUN

Factor, 73 bytes
USING: io.files io.encodings
[ 0 "a" utf8 set-file-contents ] [ t ] while

Sets the file contents to the nul byte forever.

Python, 32 bytes
while 1:open("a","w").write("b")

Note that if run on python 3, this will produce an infinite number of warnings. Also, it will probably run out of fds if run in a non-refcounting implementation.

Just as a note, a shorter answer exists without the write and the "w" part of the open command.

Dyalog APL 15.0, 17 bytes (non-competing)
(⊢⊣⊃⎕NPUT⊢)⍣≢'A'1

Chrome currently renders U+2262 wrong. The above line should look like (⊢⊣⊃⎕NPUT⊢)⍣̸≡'A'1.
This is non-competing because version 15 has not been released yet.
Applies ⍣ the function (⊢⊣⊃⎕NPUT⊢) on 'A'1 until the input is changed (i.e. never):
⊢⊣⊃⎕NPUT⊢ is a function train:
┌─┼───┐
⊢ ⊣ ┌─┼─────┐
    ⊃ ⎕NPUT ⊢

The rightmost ⊢ returns 'A'1 unmodified; this (filename, overwrite-flag) will be the right argument to `⎕NPUT'.
'⊃' returns the first element of 'A'1 ('A'); this is the data to be written.
Then ⎕NPUT is run, and reports how many bytes were written (2 or 3 depending on OS); this becomes the right argument to the ⊣.
The leftmost ⊢ again returns 'A'1 unmodified; this is the left argument to the ⊢.
⊣ ignores its right argument and returns the left argument ('A'1), this becomes the new value fed to ⍣.
Since the new value is identical to the old one, the operation is continued (forever).

SmileBASIC, 12 bytes
SAVE"A
EXEC.

Doesn’t it run out of cassette tape though?

vim text editor, 10 bytes
qa:w<enter>@aq@a

8 bytes if you do not could the execution command @a

Lua, 39 bytes
while''do io.open('a',"w"):write('')end

C++, 61 bytes.  (or 66 bytes to actually hit the disk on Linux+XFS+lazytime)
Timestamp metadata I/O only:
#include <fstream>
int main(){for(;;){std::ofstream a("a");}}

The disk I/O is due to a's mod time changing, which will be written to disk occasionally.  (very occasionally with the commonly-use lazytime mount option.  Also see my C answer.)

Write data before closing:
#include <fstream>
int main(){for(;;){std::ofstream a("a");a<<4;}}

Actually hits the disk: lights up my hard drive light.  (Linux 4.2.0, XFS, lazytime)

The ofstream constructor opens the file, and the destructor closes it again.  There are no resource leaks, so this will actually run forever without running out of memory, file handles, or disk space.
strace output:
open("a", O_WRONLY|O_CREAT|O_TRUNC, 0666) = 3
write(3, "4", 1)                        = 1      # not present with first version
close(3)                                = 0
... repeating

C99, 84 bytes
#include<stdio.h>
int main(){while(1){FILE*f=fopen("a","w");fputc(9,f);fclose(f);};}

If you don't care about buffers, you can do this instead:

C99, 65 bytes
#include<stdio.h>
int main(){while(1){fputc(9,fopen("a","w"));};}

I don't know if it closes automatically (no file handle), so please comment and I'll edit.

Lots of \ts to write (relax, they're not infinite!).

Tcl, 36 bytes
set f [open a w]
while 1 {puts $f .}

Try it online!

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Ravenity of Cube Distance Numbers
Inspired by this Numberphile entry
Background
The cube distance numbers of an integer n are defined here as the set of integers that are x³ distance away for a given x. For a simple example, with n=100 and x=2, the cube distance numbers are {92,108}.
This can be extended into a larger set simply by varying x. With x ∈ {1,2,3,4} and the same n=100, we have the resultant set {36,73,92,99,101,108,127,164}.
Let's define CD(n,x) as the set of all integers n ± z³ with z ∈ {1,2,3,...,x}.
Now we can focus on some of the special properties of these cube distance numbers. Of the many special properties that numbers can have, the two properties we're interested in here are primality and prime divisors.
For the above example CD(100,4), note that 73, 101, 127 are all prime. If we remove those from the set, we're left with {36,92,99,108,164}. All prime divisors of these numbers are (in order) {2,2,3,3,2,2,23,3,3,11,2,2,3,3,3,2,2,41}, which means we have 5 distinct prime divisors {2,3,23,11,41}. We can therefore define that CD(100,4) has ravenity1 of 5.
The challenge here is to write a function or program, in the fewest bytes, that outputs the ravenity of a given input.
Input

Two positive integers, n and x, in any convenient format.

Output

A single integer describing the ravenity of the two input numbers, when calculated with CD(n,x).

Rules

Input/output can be via any suitable method.
Standard loophole restrictions apply.
For ease of calculation, you can assume that the input data will be such that CD(n,x) will only have positive numbers in the set (i.e., no CD(n,x) will ever have negative numbers or zero).
The function or program should be able to handle input numbers so that n + x³ fits in your language's native integer data type. For example, for a 32-bit signed integer type, all input numbers with n + x³ < 2147483648 are possible.

Examples
n,x   - output
2,1   - 0   (since CD(2,1)={1,3}, distinct prime divisors={}, ravenity=0)
5,1   - 2
100,4 - 5
720,6 - 11

Footnotes
1 - So named because we're not interested in the cardinality of the set, but a different type of bird. Since we're dealing with "common" divisors, I chose to use the common raven.

How does 100,4 yield 5? The cube distance numbers of that set are 36,164, and the prime factors of that set are 2,3,41 (since the factors of that set are {2, 3, 4, 6, 9, 12, 18, 36} and {2, 4, 41, 82, 164} , respectively). Therefore, the output should be 3, not 5.

@R.Kap 100,4 is the example the OP explains in the Background section. Your mistake seems to be that you should consider all 1..x, so [1,2,3,4] for this case.

@FryAmTheEggman Oh. okay. I get it now.

Would it be pronounced [ruh-VEE-nuh-tee] (or /rəˈviːnəti/ for those of you who read IPA)?

@KennyLau In my head, I pronounced it as "rah-VIN-eh-ty"

I take it as a yes.

Jelly, 16 bytes
ŒRḟ0*3+µÆfFœ-µQL

Takes x and n as command-line arguments, in that order. Try it online!
How it works
ŒRḟ0*3+µÆfFœ-µQL  Main link. Arguments, x, n

ŒR                Range; yield [-x, ..., x].
  ḟ0              Filter out 0.
    *3            Cube each remaining integer.
      +           Add n to all cubes.
       µ          Begin a new, monadic link. Argument: A (list of sums)
        Æf        Factorize each k in A.
          F       Flatten the resulting, nested list.
           œ-     Perform multiset difference with A.
                  If k in A is prime, Æf returns [k], adding on k too many to the
                  flat list. Multiset difference with A removes exactly one k from
                  the results, thus getting rid of primes.
                  If k is composite (or 1), it cannot appear in the primes in the
                  flat list, so subtracting it does nothing.
             µ    Begin a new, monadic link. Argument: D (list of prime divisors)
              Q   Unique; deduplicate D.
               L  Compute the length of the result.

Pyth - 21 19 18 bytes
I wonder if there's a trick.
l{st#mP+Q^d3s_BMSE

Test Suite.
l                   Length
 {                  Uniquify
  s                 Combine divisor lists
   t#               Filter by if more than one element
     PM             Take prime factorization of each number
       +RQ          Add each num in list to input
          s_BM      Each num in list and its negative (with bifurcate)
              ^R3   Cube each num in list
                 SE Inclusive unary range - [1, 2, 3,... n] to input

Julia, 107 bytes
f(n,x)=endof(∪(foldl(vcat,map(k->[keys(factor(k))...],filter(i->!isprime(i),[n+z^3for z=[-x:-1;1:x]])))))

This is a function that accepts two integers and returns an integer.
Ungolfed:
function f(n, x)
    # Get all cube distance numbers
    cubedist = [n + z^3 for z = [-x:-1; 1:x]]

    # Filter out the primes and zeros
    noprimes = filter(i -> !isprime(i) && i > 0, cubedist)

    # Factor each remaining number
    factors = map(k -> [keys(factor(k))...], noprimes)

    # Flatten the list of factors
    flat = foldl(vcat, factors)

    # Return the number of unique elements
    return endof(∪(flat))
end

The spec has been updated; you don't have to worry about 0's anymore.

@Dennis Nice, thanks for the heads up.

J, 30 bytes
#@~.@(,@:q:-.0&,)@:+(|#^&3)@i:

This is a dyadic verb, used as follows:
   f =: #@~.@(,@:q:-.0&,)@:+(|#^&3)@i:
   100 f 4
5

Try it here.
Explanation
#@~.@(,@:q:-.0&,)@:+(|#^&3)@i:
                            i:  Range from -x to x
                    (     )@    Apply this verb to the range:
                       ^&3        a) every item cubed
                     |            b) absolute value of every item
                      #           c) every item in a) repeated b) times; this removes 0
                                     and produces some harmless duplication
                   +            Add n to every element of the resulting list
     (          )@:             Apply this verb to the resulting vector:
             0&,                  a) the vector with 0 appended
      ,@:q:                       b) flat list of prime divisors in the vector
                                     (and some extra 0s since we flatten an un-even matrix)
           -.                     c) list b) with elements of a) removed; this gets rid of
                                     the extra 0s and all primes that were in the list
#@~.@                           Remove duplicates and take length

@:+( why so sad, awesome-hair-guy?

Link to TIO in answer please?

@EasterlyIrk TIO doesn't have J. I'll add a link to tryj.tk.

@Zgarb okai.___

MATL, 21 bytes
:3^t_h+tZp~)"@Yf!]vun

Input is x, n separated by a newline.
Try it online!
Explanation
:       % take n implicitly. Generate [1,2,...,n]
3^      % raise to 3, element-wise
t_h     % duplicate, negate, concatenate horizontally: [1,2,...,n,-1,2,...-n]
+       % take x implicitly. Add to that array
t       % duplicate
Zp      % array that contains true for primes
~       % logical negate
)       % apply index to keep only non-primes
"       % for each number in that array
  @     %   push that number
  Yf!   %   prime factors, as a column array
]       % end for each
v       % concatenate vertically all factors
u       % remove repeated factors
n       % number of elements of that array. Implicitly display

05AB1E, 20 19 bytes
Code:
L3mD(«-Dp_Ïvyf`})Úg

Input in the form x, n. Uses CP-1252 encoding.
Try it online!

Python 3.5, 218 198 bytes:
(Thanks to @Blue for saving me 20 bytes.)
lambda r,n:len({z for z in{v for f in{t for u in[[r-q**3,r+q**3]for q in range(1,n+1)]for t in u if any(t%g<1 for g in range(2,t))}for v in range(2,f)if f%v<1}if all(z%g>0 for g in range(2,z))})

A nice one-lined lambda function, although it may be a bit long. Since I was using Python, I had to come up with my own way of finding the composites for the first step, and then the prime divisors for the last step, so it was not very easy, and this was the shortest I, by myself. could get it to. Nonetheless, it does what it needs to, and I am proud of it. :) However, any tips for golfing this down a bit more are welcome.

Couple things: don't use ==0, use <1, and for !=0, >0. Also, why the z%1 and z%z at the end? Those seem like they will always be true.

@Blue Yeah, you're right. They will always be true, so that part is not even needed. So, I'll remove that. And also, thanks for those other tips! :)

Ruby, 132 120 114 bytes
I'm well aware that this solution still needs a lot of golfing. Any golfing tips are welcome.
require'prime'
->n,x{(-x..x).map{|i|j=n+i**3;j.prime?||(j==n)?[]:j.prime_division.map{|z|z[0]}}.flatten.uniq.size}

Ungolfing:
require 'prime'

def ravenity(n, x)
  z = []
  (-x..x).each do |i|
    j = n + i**3
    m = j.prime_division
    if j.prime? || j == n
      z << []
    else
      z << m.map{|q| q[0]}
    end
  return z.flatten.uniq.size
end

PARI/GP, 79 bytes
(n,x)->omega(factorback(select(k->!isprime(k),vector(2*x,i,n+(i-(i<=x)-x)^3))))

Here is my original straightforward implementation. The optimized version above combines the two vectors into a single, slightly more complicated vector.
(n,x)->omega(factorback(select(k->!isprime(k),concat(vector(x,i,n-i^3),vector(x,i,n+i^3)))))

This is really interesting. I see there's an in-browser link to try the code, but I'm not sure how to actually submit the input. Can you provide an explanation?

@TimmyD: If you assign either of the above to f (like f=(n,x)->...) then you can test it with f(100,4). Alternately, you can invoke it in one line with ((n,x)->...)(100,4).

Ruby, 138 bytes
->(n,x){require'prime'
v=((-x..x).to_a-[0]).map{|i|n+i**3}.reject{|e|Prime.prime?(e)}
Prime.each(v[-1]).select{|i|v.any?{|e|e%i==0}}.size}

It was a puny challenge. :-)

They seriously have a built in way to find primes in Ruby? Wow...I can't believe Python does not have that.

Yup. See http://ruby-doc.org/stdlib-2.3.0/libdoc/prime/rdoc/Prime.html - Should work even in version 1.9.3.

Python 3.5 - 177 175 159 bytes
Any golfing tips welcome :)
a=range
p=lambda n:any(n%x<1for x in a(2,n))
r=lambda n,x:len(set(sum([[x for x in a(2,z+1)if z%x<1&1>p(x)]for z in filter(p,[n+z**3for z in a(-x,x+1)])],[])))

Ungolfed:
def is_composite(n):
    return any(n % x == 0 for x in range(2, n))

def prime_factors(n):
    return {x for x in range(2, n+1) if n % x == 0 and not is_composite(x)}

def ravenity(n, x):
    nums = [n + z**3 for z in range(-x, x+1)]
    nums = filter(is_composite, nums)
    factors = map(prime_factors, nums)
    factors = sum(factors, [])
    #remove duplicates
    factors = set(factors)
    return len(factors)

Wolfram Language (Mathematica), 90 bytes
Tr[1^Union[First/@Join@@FactorInteger/@Select[z=Range@#2^3;Join@@{#-z,#+z},Not@*PrimeQ]]]&

Try it online!
un-golfed: the code is read mostly from right to left,
F[n_, x_] :=
  Length[Union[                                        (* number of unique elements   *)
    First /@                                           (* drop multiplicities         *)
      Join @@                                          (* join all prime factor lists *)
        FactorInteger /@                               (* compute prime factors       *)
          Select[                                      (* select those...             *)
            Join @@ {n - Range[x]^3, n + Range[x]^3},  (* ...candidates...            *)
            Not@*PrimeQ]]]                             (* ...that are not prime       *)

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Is this a Lucas number?
Write a program or function that takes an input greater than or equal to 2. It should output a truthy or falsy value corresponding to whether the input is a Lucas number or not. You may take input from STDIN, or whichever source is most suitable to you.
This question is different to this one because this question is specifically for Lucas numbers only, and not Fibonacci numbers at all, whereas that question was Lucas number, Fibonacci numbers and both possible combinations of them. This question was, however, inspired by that question and is similar in some regards.
Lucas numbers are the numbers that result from the rules following: the first Lucas number is a 2, the second is a 1, and each term after that is the sum of the previous two. Yes, it is very similar to the Fibonacci sequence, but this has the added advantage of converging closer to the golden ratio, phi, faster than Fibonacci numbers do.
Example inputs/outputs
Input   Output
--------------
3       True
4       True
7       True
8      False
10     False
3421   False
9349    True

etc.
Some limitations

Your program/function must run in a reasonable amount of time. It should terminate within seconds and minutes, not hours and days.
Your program must not calculate all the Lucas numbers up to the input number

This is code golf, so the shortest code in bytes wins.

This is a subtask of this challenge.

Yup. I was heavily inspired by that one.

MATL, 19 17 16 18 bytes
2^5*20t_h+X^Xj1\~a

Try it Online!
Explanation
2^          % Implicitly grab the input and square it
5*          % Multiply the result by 5
20          % Create the literal number 20
t_          % Duplicate and negate the second 20
h           % Concatenate 20 and -20 to get [20 -20]
+           % Add the array to the result of 5*n^2
X^          % Compute the square root
Xj          % Ensure that the result is a real number
1\          % Compute the remainder to test for perfect squares
~a          % Check to see if any had a remainder of zero (returns a boolean)

Python, 69 67 53 characters
lambda x:0in(((5*x**2+20)**.5)%1,((5*x**2-20)**.5)%1)

This works in both Python 2.x and 3.x.
See this answer to see how it works - n is a Lucas number if either 5n^2+20 or 5n^2-20 is a perfect square. My program checks to see if either of their square roots are integers and checks if 0 is in the tuple that results.

Python, 45 43 characters
lambda n:0in[(5*n*n+k)**.5%1for k in-20,20]

Based on a proof given here.

I knew there was a shorter way in Python! Your answer has given me insight in golfing, as I am relatively new to this art. Thanks.

MATLAB, 43 bytes
@(n)~all(rem(real(sqrt(5*n^2+[-20 20])),1))

Inspired by Anders Kaseorg's answer


text:
Write an interpreter for my new programming language
I have a new programming language called Brussels-Sprout. Brussels-Sprout functions in an array of 256 boolean values, all initialized to zero, has one instruction pointer, and one "bit index".
After each (non-branching) instruction is executed, the instruction pointer is incremented by one. If the instruction pointer goes off the right side of the instruction array, the program terminates. Going off the left side is undefined behavior.
If the bit index is outside the bounds of the array, it should be reset to 0.
Brussels-Sprout uses the following keywords, which are always lowercase:
chew - Invert the value in the array at the bit index. (flip the bit at the bit index)
swallow - Increment the bit index.
vomit - Decrement the bit index.
complain - Output the bit at the bit index to stdout, or equivalent output log.
feedtodog - If the bit at the bit index is 0, skip the next instruction. Otherwise, increment instruction pointer by 1.
playwithfood - If the bit at the bit index is 1, jump backwards 2 instructions. Otherwise, increment instruction pointer by 1.
If an instruction not on this list is executed, undefined behavior occurs.
I'm sure that this sounds like a very certain other turing-tarpit programming language. But since this programming language operates in boolean values and not bytes, I think it is different.
Test cases:
chew complain -> 1
swallow chew swallow chew swallow vomit complain playwithfood -> 11
chew complain swallow chew complain swallow chew complain swallow complain -> 1110
chew feedtodog undefinedbehaviour complain -> 1

Your challenge is to write an interpreter for Brussels-Sprout. This is code golf, so shortest program wins!

How do we get the input?  Can we take it as a list?

And do all the bits start at 0 or 1?

If those are the only options for interacting with Brussels sprouts, clearly you haven't had them roasted with olive oil, salt, and pepper.

Hey Mason! It is nice that you want to contribute to this site, but writing a good challenge is not easy and also requires some experience. 2 of your 3 challenges got closed so far and this one might be put on hold for being unclear as well. I would really recommend that you use the sandbox in the future, so you can get feedback and work potential flaws out before you post your challenge to the main site. However, I hope you stick around and have a great time here!

Also you should really add some testscases, since this is not a very trivial task to solve and it's hard to say if a potential solution works correctly. But please note that testcases are not a replacement for a clear specification of the I/O formats which is definitely missing here.

@AlexA. Mmmm. Fried in coconut oil with garlic, a bit of ginger, and a dash of Tabasco.

You should specify what happens if unknown instructions are provided. My answer quits the program when they are found. CatsAreFluffy's answer may execute arbitrary existing instructions or just quit the program.

Why is this closed?

@CatsAreFluffy Probably because it is underspecified, which is sad but true. It doesn't says for example, what would happen if it branches to outside the instruction array (something that we both exploited for halting) nor it specified what would happen if an invalid instruction is given (a hole that both your answer and my new answer exploits for golfing). Also, it lacks test cases, which are very important to give confindence against possibly buggy interpreters.

A few test cases and some specification.

@CatsAreFluffy I think that chew swallow chew swallow vomit complain playwithfood is an infinite loop, because playwithfood would go back two instructions to vomit. And this would loop the sequence vomit complain playwithfood forever. The vomit instruction will keep decrementing the bit index forever, but it would be kept resetted to zero everytime that it tries to go to -1 (which is outside the bounds of the array). My interpreter loops forever on that keeping outputting 1s continuously forever.

Oops, please swallow once before running that program. But undefinedbehavior should not be in a testcase.

Is this reopenable now?

This testcase "swallow chew swallow chew swallow vomit complain playwithfood -> 11" is wrong, the output is 110 because it does the vomit/complain/play loop as it walks back through 1s until 0, but it still does the vomit/complain/play on the 0 value and vomits that one as well.

Python 3 2, 200 187 149 146 136 bytes
-9bytes thanks to Cyoce
def f(n,a=[0]*256,x=0,z=0):
 while 1:y=a[z];exec'a[z]^=~1 z+=1 z-=1 print-y/2 if~y:x+=1 if~~y:x-=3'.split()["wlipdy".find(n[x][3])];x+=1

Input as list, exits by error. Bonus feature: you can specify start array, start IP, and start DP in that very exact order.

A few suggestions: first, x=0;z=0 can be x=z=0. Second, a=[0 for x in range(256)] can be a=[0]*256. Third, instead of the if statement chain, use a dictionary of strings then use exec on the result.

Did #1, I didn't know #2, considered #3.

Goodbye bytes! (I miss my fluffy)

Well 0 and -1, but yes, but I just got rid of those. But buts are confusing, but they're fun, so yeah.

I think you can save a few bytes by switching to Python 2 if you're interested (you can remove the parens on print and exec)

-3 bytes. I'll take it.

your solution seems to be complaining -2 instead of 1.

...-2? How? It should only spit out 0 and -1.

fixed version, saved bytes (replace the dictionary method with this): 'a[z]^=~1|z+=1|z-=1|print -y/2|if~y:x+=1|if y:x-=3'.split('|')["wlipdy".find(n[x][3])]

Implementing. But what program spat out -2?

Aaugh, it does it every time. But still -3 more bytes: drop the space after  print and use ~~ in the last if to allow split().

Apparently + works instead.

SpecBAS (modern Sinclair BASIC interpreter) 202 Bytes
1 INPUT a$:DIM b(256)BASE 0,i$(),a$(SPLIT a$," "):DO 6:READ b,i$(b):LOOP:b=0,i=1:DO:c=b(b):EXECUTE i$(CODE a$(i,4)-99):b&=255,i+=1:LOOP:DATA 20,"b(b)=1-c",9,"b+=1",6,"b-=1",13,"?c;",1,"i+=c",22,"i-=3*c"

Or to make it a little clearer:
1 INPUT a$:
  DIM b(256) BASE 0,i$(),a$(SPLIT a$," "):
  DO 6:
    READ b,i$(b):
  LOOP:
  b=0,i=1:
  DO:
    c=b(b):
    EXECUTE i$(CODE a$(i,4)-99):
    b&=255,i+=1:
  LOOP:
  DATA 20,"b(b)=1-c",9,"b+=1",6,"b-=1",13,"?c;",1,"i+=c",22,"i-=3*c"

Uses some features that weren't available in the 80s, so there's that. Also shameless rips off some of the techniques in other entries. Sorry about that!
Input is from the user at runtime. Execution ends with an error "Subscript wrong".

Java 8
1. Relaxed version (301 283 280 277 275 bytes)
Golfed as this:
class C{static int i,j,x,b[]=new int[256];public static void main(String[]z){Runnable[]r=new Runnable[26];r[20]=()->b[i]=-~x;r[9]=()->i++;r[6]=()->i--;r[13]=()->System.out.print(x);r[1]=()->j+=x;r[22]=()->j-=3*x;for(;;){x=b[i];r[z[j].charAt(3)-99].run();i*=~(i>>8)&1;j++;}}}

Somewhat ungolfed version (whitespaces and comments added):
class C {
    // Declared as static so they may be changed inside the lambdas without the compiler complaining about that.
    // i is the bit index and j is the instruction pointer.
    // x is just to avoid refering to b[i] in order to save 3 bytes.
    // b is our array. Uses ints instead of booleans to save bytes and use some clever math tricks.
    static int i, j, x, b[] = new int[256];

    public static void main(String[] z) {

        // An array of lambdas. The index is the ascii code of 4th letter of the command name subtracted from 99.
        // Thanks for CatsAreFluffy for telling about the 4th letter trick.
        Runnable[] r = new Runnable[26];
        r[20] = () -> b[i] = -~x; // chew
        r[9] = () -> i++; // swallow
        r[6] = () -> i--; // vomit
        r[13] = () -> System.out.print(x); // complain
        r[1] = () -> j += x; // feedtodog. It is 1 or 0 instead of 2 and 1 due to the j++ down there.
        r[22] = () -> j -= 3 * x; // playwithfood. It is -3 or 0 instead of -2 and +1 due to the j++ down there.

        // This is the interpreter itself. Runs forever (or until an exception is raised).
        for (;;) {
            x = b[i];

            // Fetch an instruction and runs it. May throw an exception or execute some arbitrary instruction if the instruction name is unknown or was mistyped.
            r[z[j].charAt(3) - 99].run();

            // Resets the bit index if out of range.
            i *= ~(i >> 8) & 1;

            // Next instruction. No special treatment for branching needed because they already considers this.
            j++;
        }
    }
}

We surely should have testcases. I am not sure if there is some bug hiding out there.
Anyway I run it with that (input is given as command line arguments):
chew complain swallow chew complain swallow chew complain swallow complain

And here is the output:
1110
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
    at C.main(C.java:1)

The ArrayIndexOutOfBoundsException is the standard way to finish the program, it is not a bug!
BTW, this answer abuses the fact that the 4th char of each command is different than each other (thanks CatsAreFluffy). This means that whew is interpreted as chew and that yellow is interpreted as swallow.
2. Strict version (354 337 334 331 329 bytes)
If strict conformance to command names are required (and just looking for the 4th letter in command's name is not enough), then I have this alternative similar answer with 329 bytes:
import java.util.*;class C{static int i,j,x,b[]=new int[256];public static void main(String[]z){List o=Arrays.asList("chew","swallow","vomit","complain","feedtodog","playwithfood");Runnable[]r={()->b[i]=-~x,()->i++,()->i--,()->System.out.print(x),()->j+=x,()->j-=3*x};for(;;){x=b[i];r[o.indexOf(z[j])].run();i*=~(i>>8)&1;j++;}}}

Somewhat ungolfed version (whitespaces and comments added):
// Needed for java.util.List and java.util.Arrays.
import java.util.*;

class C {
    // Declared as static so they may be changed inside the lambdas without the compiler complaining about that.
    // i is the bit index and j is the instruction pointer.
    // x is just to avoid refering to b[i] in order to save 3 bytes.
    // b is our array. Uses ints instead of booleans to save bytes and use some clever math tricks.
    static int i, j, x, b[] = new int[256];

    public static void main(String[] z) {

        // Declared as a list so we can use the indexOf method further down. Screw up the generics.
        List o = Arrays.asList("chew", "swallow", "vomit", "complain", "feedtodog", "playwithfood");

        // An array of lambdas.
        Runnable[] r = {
            () -> b[i] = -~x, // chew
            () -> i++, // swallow
            () -> i--, // vomit
            () -> System.out.print(x), // complain
            () -> j += x, // feedtodog. It is 1 and 0 instead of 2 and 1 due to the j++ down there.
            () -> j -= 3 * x // playwithfood. It is -3 and 0 instead of -2 and +1 due to the j++ down there.
        };

        // This is the interpreter itself. Runs forever (or until an exception is raised).
        for (;;) {
            x = b[i];

            // Fetch an instruction and runs it. Throws an exception on unknown or mistyped instructions.
            r[o.indexOf(z[j])].run();

            // Resets the bit index if out of range.
            i *= ~(i >> 8) & 1;

            // Next instruction. No special treatment for branching needed because the branching instructions already considers this.
            j++;
        }
    }
}

I don't Java, but can you shorten the list of strings by using a separator then splitting it into an array? i.e. javaSplitFunction("chew|swallow|vomit|complain|feedtodog|playwithfood|")

@Cyoce I could simply use an array instead and it would be easier and shorter, but then this screws me up further down when I have to use the List.indexOf method. To fix that screw-up, I would end with a longer answer.

Can you use a HashMap from Strings (or char) to Runnables? The fourth char of each command is distinct.

@Cyoce No, because doing that would violate java's type system and produce a compile error. :(

@CatsAreFluffy Edited. Thanks. :)

Your strict answer is no longer "older'.

@CatsAreFluffy Yes. Now I maintain the two versions. The relaxed is if the 4th char trick is allowed by the OP and the strict if it is not. :D

@VictorStafusa nevermind I'm stupid I forgot those were booleans.

The spec says that unknown words are undefined behavior, so the relaxed version is valid. Also, please add a bytecount tot he title (it breaks the graduation userscript leaderboard otherwise)

262 bytes

Ruby 2, 151 bytes
Saw this because of another golf challenge and was amused enough by it to write it up in Ruby, and was happy to see it got very close to the Python answer (Ruby usually doesn't golf compress quite as well as Python).
b=[n=i=0]*256
r=''
(x=b[i=b[i]?i:0]
eval({?w=>'b[i]=1-x',?l=>'i+=1',?i=>'i-=1',?p=>'r<<x.to_s',?d=>'n+=-x',?y=>'n+=x*-3'}[c[n][3]])
n+=1)while(c[n])
r

You can put this in a function def that takes 'c' as a list of the commands, and it returns 'r' as the last line which is the result string.
Runs the testcases properly (if the second one is updated to actually output 110 instead of 11 as it currently incorrectly claims is the right answer - see my comment above).